Complejidad de un algoritmo

Vista previa del material en texto

Cuando hablamos de la complejidad de un algoritmo, es común utilizar la notación Big O. La 
notación Big O proporciona una forma estandarizada de describir el crecimiento asintótico del 
tiempo de ejecución o el uso de recursos a medida que el tamaño del problema aumenta. 
 
La notación Big O se utiliza para establecer límites superiores en la complejidad de un 
algoritmo. En otras palabras, nos da una idea de cómo crece la eficiencia del algoritmo en el 
peor de los casos. Se representa mediante la letra "O" seguida de una expresión que describe 
la función de crecimiento del algoritmo en función del tamaño de la entrada. 
 
Por ejemplo, si decimos que el tiempo de ejecución de un algoritmo es O(n), esto significa que 
el tiempo de ejecución del algoritmo crece linealmente con el tamaño de la entrada. Si el 
tamaño de la entrada se duplica, el tiempo de ejecución también se duplicará. 
 
Es importante destacar que la notación Big O se enfoca en el crecimiento asintótico, lo cual 
significa que considera cómo se comporta el algoritmo cuando el tamaño del problema se 
acerca al infinito. Esto nos permite hacer análisis comparativos y determinar qué algoritmos 
son más eficientes en general. 
 
Algunos ejemplos comunes de notación Big O son: 
 
O(1): Tiempo constante. El algoritmo tiene un tiempo de ejecución constante, 
independientemente del tamaño de la entrada. 
O(log n): Tiempo logarítmico. El tiempo de ejecución crece de forma logarítmica a medida que 
el tamaño de la entrada aumenta. 
O(n): Tiempo lineal. El tiempo de ejecución crece de forma proporcional al tamaño de la 
entrada. 
O(n^2): Tiempo cuadrático. El tiempo de ejecución crece cuadráticamente a medida que el 
tamaño de la entrada aumenta. 
O(2^n): Tiempo exponencial. El tiempo de ejecución crece de forma exponencial a medida que 
el tamaño de la entrada aumenta. 
Es importante destacar que la notación Big O nos permite comparar algoritmos y determinar 
cuál es más eficiente en términos de su crecimiento asintótico. Sin embargo, es fundamental 
tener en cuenta que la notación Big O no nos dice nada sobre los factores constantes o las 
características específicas del hardware y del entorno de ejecución. Por lo tanto, dos 
algoritmos con la misma notación Big O pueden tener diferencias significativas en su tiempo 
de ejecución real. 
 
En resumen, la notación Big O se utiliza para describir la complejidad de un algoritmo y 
proporcionar una estimación del crecimiento asintótico del tiempo de ejecución o el uso de 
recursos a medida que el tamaño del problema aumenta. La notación Big O nos permite 
comparar y analizar algoritmos en términos de su eficiencia relativa. Sin embargo, es 
importante recordar que la notación Big O no tiene en cuenta los factores constantes y las 
características específicas del entorno de ejecución.