¿Qué es la notación Big O?
La notación Big O es uno de esos temas que todos deberíamos de conocer como Ingenieros de Software, sin embargo en ocasiones puede resultar confuso o no necesario porque -qué importa, mi código ya funciona!.
Probablemente dije eso más de una vez y después de encontrarme ese tema en múltiples ejercicios de entrevistas de trabajo de empresas Oracle o Uber finalmente decidí estudiar y recopilar información acerca del mismo. En este post discutiremos Big O junto con algunos de los ejemplos más comunes.
Definición
La notación Big O es la representación relativa de la complejidad de un algoritmo.
¿Por qué es importante?
Con el poder computacional que tenemos hoy en día un algoritmo que tenga como entrada un grupo de datos pequeño o mediano puede terminar en un tiempo aceptable, sin embargo si no analizamos su complejidad no estaremos seguros si el algoritmo funcionará con un grupo de datos grande (como algunos millones de datos).
NOTACION BIG O
La notación Big O es una herramienta para determinar la complejidad de un algoritmo que estemos utilizando, permitiéndonos medir su rendimiento en cuanto a uso de espacio en disco, recursos “memoria y ciclos del reloj del CPU” y tiempo de ejecución, entre otras, ayudándonos a identificar el peor escenario donde el algoritmo llegue a su más alto punto de exigencia.
Los términos de complejidad Big O más utilizados son:
- O(1) -> constante.
- O(n) -> linear.
- O(log n) -> logarítmica.
- O(n ^ 2) -> cuadrática.
- O(2 ^ n) -> exponencial.