Notación big O

Para analizar el rendimiento de un algoritmo de un modo sencillo, se usa la notación Big O, lo cual es una forma matemática básica de expresar cuanto tarda un algoritmo en ejecutarse atendiendo sólo a grandes rasgos su eficiencia y así poder compararlo con otros. En definitiva evaluar su complejidad y poner nota a su eficiencia.

En concreto se usa para expresar de forma abstracta la velocidad de procesamiento de un algoritmo, atendiendo a cómo aumentaría su tiempo de ejecución en función de un aumento significativo del tamaño de los datos de entrada.

A grandes rasgos, es útil para evaluar cómo es la curva de crecimiento de su tiempo de ejecución conforme aumentan el tamaño del input de entrada. Por ejemplo, si los datos de entrada se duplican, ¿lo hará también al doble el tiempo de ejecución del algoritmo?

Realmente el tiempo exacto de ejecución de un algoritmo es algo dificil de medir ya que depende de la velocidad del procesador y de lo ocupado que esté, por lo que el uso de la notación Big O es para únicamente fijarnos en cómo de rápido se incrementa el tiempo en función del crecimiento de los datos de entrada.

Por tanto, no usaremos segundos, y sólo una expresión matemática de cómo crece el tiempo en función del tamaño del input. Así que para una entrada abstracta dada que denominaremos de magnitud N, con la notación Big O definimos cómo aumenta el tiempo del algoritmo conforme N se hace cada véz más y más grande.

Se trata de un análisis asintótico, refiriendome con ello a que nos fijamos en qué ocurre hacia el límite, lo que ocurre hacia el infinito, y no tanto con valores pequeños, por lo que así es más facil el análisis. Lo mejor es verlo en una gráfica, en la que representamos el tiempo de ejecución frente al tamaño de los valores de entrada al algoritmo.

La O viene de clasificar el ORDEN de magnitud de la función a analizar, resumiendose en que nos sirve para determinar cómo un algoritmo escala en complejidad tanto en tiempo como en espacio necesario, en función de su tamaño de entrada.

Podemos resumir la nota dada a unos poco valores, ya que descartamos las constantes y sólo atendemos a unos pocos casos según el orden de magnitud de crecimiento, y sin importar por ejemplo el detalle de la inclinación de cada curva y sólo la forma de comportamiento de crecimiento. En resumen, nos podemos quedar con que tenemos:

• O(1) - Tiempo constante: es el mejor resultado, y quiere decir que el tiempo de ejecución no varía conforme aumenta el tamaño de los datos de entrada, y la respuesta siempre tarda lo mismo sin importar la magnitud de entrada.
• O(n) - Tiempo lineal: el crecimiento es lineal en tanto el tiempo de ejecución es cada vez mayor de modo proporcional a cómo se incrementa el tamaño de la entrada. Por lo que si tenemos el doble de elementos de entrada, tardará el doble, aunque despreciamos realmente la pendiente de la misma y sólo nos quedamos con que aumenta de forma lineal.
• O(log n) - tiempo logarítmico: una forma de crecimiento que crece al inicio pero tiende a estabilizarse conforme aumentan el tamaño de entrada, por lo que es una buena nota para un algoritmo ya que no tiende a resentirse.
• O(n2) - tiempo cuadrático: el crecimiento es de forma exponencial por lo que será un algoritmo a evitar ya que para valores pequeños de entrada el tiempo será asumible, pero conforme aumente el tamaño de los datos de entrada el tiempo tenderá a ser muy elevado y es probable que el procesador se quede inoperativo.
• O(n!) - tiempo factorial: el crecimiento es factorial, por lo que rápidamente tiende a valores imposibles de tratar, en lo que sería una recta vertical.

Lo mejor para terminar de asimilarlo es evaluar ejemplos concretos de cómo funcionan los bucles, diferentes métodos de busqueda, estructuras de datos,.. y ejemplos concretos en cada situación que te ayuden a tener algo en cuenta todo esto cuando programes.

En resumen, la notación Big O es una notación matemática que nos sirve para poner nota a la velocidad de procesamiento de un algoritmo atendiendo a cómo se comporta conforme aumenta el tamaño del trabajo a procesar, por lo que nos sirve para clasificar la eficacia de los mismos. Útil tanto para valorar la necesidades de procesamiento como de espacio necesario para llevar a cabo el algoritmo, y en definitiva valorar qué tan bueno es un algoritmo dado para resolver problemas muy grandes, ya que aparentemente puede ser bueno para unos valores dados, pero fallar según escala el tamaño de entrada:

• Qué: la notación Big O es una forma de poner nota a la eficiencia de un algoritmo
• Cuanto: sólo necesitamos simplificar a si es constante, lineal, logarítmica o cuadrática
• Dónde: en el análisis de algoritmos de programación, tanto tiempo como espacio necesario
• Cuándo: queremos evaluar y/o comparar la eficacia de un algoritmo, estructura de datos,...
• Cómo: comparando la velocidad de crecimiento de una magnitud (tiempo) respecto la otra (tamaño entrada)
• Por qué: necesitamos valorar la viabilidad de nuestras soluciones en determinadas situaciones

Si te ha gustado... ¡Compártelo!