Complejidad Temporal y Espacial

Vista previa del material en texto

Complejidad Temporal y Espacial: Medición de Eficiencia con Notación Big O 
 
La complejidad temporal y espacial son conceptos fundamentales para evaluar la eficiencia de 
los algoritmos y las estructuras de datos en términos de tiempo de ejecución y uso de 
memoria. La notación Big O es una herramienta clave para expresar estas complejidades y 
comparar la eficiencia relativa de diferentes enfoques. En este resumen, exploraremos el 
concepto de Big O notation, cómo se aplica para medir la complejidad temporal y espacial, y 
cómo evaluar la eficiencia de diferentes algoritmos y estructuras de datos. 
 
Complejidad Temporal y Espacial: 
 
Complejidad Temporal: Se refiere al tiempo que un algoritmo tarda en completar su ejecución 
en función del tamaño de la entrada. Se mide en términos de número de operaciones 
elementales realizadas por el algoritmo. 
 
Complejidad Espacial: Se refiere al espacio (memoria) que un algoritmo utiliza para su 
ejecución en función del tamaño de la entrada. Se mide en términos de cantidad de memoria 
utilizada. 
 
Notación Big O: 
 
La notación Big O se utiliza para describir el límite superior asintótico de la complejidad 
temporal o espacial de un algoritmo en términos de la función de tamaño de entrada (n). Por 
ejemplo: 
 
O(1): Complejidad constante. El tiempo o el espacio no varían con el tamaño de entrada. 
O(log n): Complejidad logarítmica. El tiempo o el espacio aumentan de manera logarítmica con 
el tamaño de entrada. 
O(n): Complejidad lineal. El tiempo o el espacio aumentan de manera proporcional al tamaño 
de entrada. 
O(n log n): Complejidad log lineal. Común en algoritmos eficientes como mergesort y heapsort. 
O(n^2), O(n^3), ...: Complejidad polinómica. El tiempo o el espacio aumentan de manera 
cuadrática, cúbica, etc., con el tamaño de entrada. 
O(2^n), O(n!): Complejidades exponencial y factorial. Generalmente son ineficientes y deben 
evitarse en la mayoría de los casos. 
Evaluación de Complejidades: 
 
Análisis de Ciclo: Para algoritmos iterativos, contar el número de ciclos y operaciones en 
función de la entrada. 
 
Recurrencias: Para algoritmos recursivos, derivar ecuaciones de recurrencia que describan la 
complejidad en términos de llamadas recursivas. 
 
Evaluación Empírica: Medir el tiempo y el espacio en ejecuciones reales para observar la 
relación con el tamaño de entrada. 
 
Comparación de Algoritmos y Estructuras de Datos: 
 
La notación Big O permite comparar la eficiencia de diferentes algoritmos y estructuras de 
datos en función del tamaño de entrada. Permite tomar decisiones informadas sobre qué 
enfoque es más adecuado para resolver un problema específico. 
 
Conclusión: 
 
La complejidad temporal y espacial son consideraciones críticas al diseñar y analizar algoritmos 
y estructuras de datos. La notación Big O proporciona una forma estandarizada de expresar y 
comparar estas complejidades. Al entender y aplicar la notación Big O, los programadores 
pueden evaluar la eficiencia relativa de diferentes enfoques y tomar decisiones informadas 
para lograr un rendimiento óptimo en sus aplicaciones y sistemas.