El Big O es una métrica utilizada en la Ingeniería de Software para determinar el nivel de eficiencia y complejidad (tanto espacial como temporal) que tendrá un algoritmo bajo altas cargas de trabajo.
<aside> 💡 ¿Qué es un algoritmo? Un algoritmo es un conjunto ordenado y finito de operaciones que permite hallar la solución de un problema. Está definido por instrucciones o reglas bien definidas, ordenadas y finitas que permiten realizar una actividad. Dado un estado inicial, una entrada y una secuencia de pasos sucesivos, se llega a un estado final y se obtiene una solución.
</aside>
La eficiencia de un algoritmo vendrá dada por su tiempo de ejecución asintótico. La notación asintótica (que viene de asíntota, definida como «Una curva que se acerca indefinidamente a una recta o a otra curva sin llegar nunca a encontrarla» ), es una forma de describir una curva matemática, una forma de evolución de un fenómeno respecto a cambios en sus factores de entrada. Las notaciones asintóticas son lenguajes que nos permiten analizar el tiempo de ejecución de un algoritmo identificando su comportamiento si el tamaño de entrada para el algoritmo aumenta. Esto también se conoce como la tasa de crecimiento de un algoritmo.
<aside> 💡 Datos de entrada: Son los datos que se brindan a un algoritmo dado para realizar el proceso o trabajo correspondiente. Un detalle importante a considerar es que, aun cuando usualmente el tamaño de la entrada se pueda medir en bytes o cantidad de datos, la realidad es que en ocasiones no se trata de la cantidad de datos sino de la laboriosidad que los datos de entrada representan para el algoritmo; por ejemplo, puede que nuestro algoritmo reciba un dato de entrada que es de un solo tamaño (digamos un entero) pero ese entero cuando es un número grande (digamos 1 millón) hace que el trabajo a realizar tome más tiempo que si se trata de un número pequeño (digamos 10 unidades).
</aside>
De las distintas anotaciones existentes, el Big O (o también llamado Notación O) es una notación asintótica que permite analizar un algoritmo por su peor caso. Esto permite describir el crecimiento de los requerimientos de recursos (ciclos de procesamiento, tiempo, memoria, almacenamiento) de un algoritmo respecto del tamaño de los datos de entrada, o más explicitamente, respecto del tamaño del trabajo a procesar.
Sin embargo, el tiempo no es el único factor importante. Se debe tener en cuenta su complejidad espacial, o dicho de otro modo, la cantidad de memoria utilizada por el algoritmo. Normalmente se hacen compromisos entre la complejidad temporal y espacial, ya que la mejora en una vendrá en detrimento de la otra. El objetivo es encontrar un buen balance entre ambas complejidades, dadas nuestras condiciones.
<aside> 💡 Tiempo de ejecución, ciclos de ejecución: Para nuestro análisis se refiere al tiempo que toma a un algoritmo realizar la tarea para la cual está diseñado. Este tiempo depende no solo del tamaño de la entrada y del diseño del algoritmo, sino también de variables tales como la velocidad del hardware entre otras. Es por esto que una medida más precisa sería ciclos de ejecución o complejidad de ejecución que define el tamaño relativo de la tarea a realizar respecto de la especificación en los datos de entrada.
</aside>
<aside> 💡 Requerimiento de espacio: En este caso se refiere a la cantidad de memoria RAM y/o memoria de almacenamiento persistente que se necesita por parte de un algoritmo dado para realizar su trabajo. Al igual que con el tiempo de ejecución, el espacio requerido no solamente depende del tamaño de la entrada o el diseño del algoritmo, sino de otras variables relacionadas con el hardware.
</aside>
Es importante tener en cuenta que el número de instrucciones u operaciones a realizar sobre los distintos inputs (entradas) no influye sobre la complejidad algorítmica. De nuevo, la complejidad algorítmica mide la forma en la que crece el tiempo de ejecución de un algoritmo según los valores de entrada.
Dado que el tiempo y ejecución de un algoritmo en base a su tamaño de entrada dependen de muchas variables (como por ejemplo, el tipo de hardware utilizado para ejecutar dicho algoritmo), es casi imposible definir un tiempo o espacio específicos. La notación asintótica permite describir cómo crecerán esos requerimientos de espacio y tiempo con respecto al tamaño de entrada recibida. Para esto, se han definido varios tipos de “órdenes” que describen las formas de crecimiento más comunes. Estos son: