Programación · conceptos · algoritmos
¿Qué es la notación Big O?
La notación Big O es una forma de describir cómo crece el tiempo de ejecución de un algoritmo (o su uso de memoria) a medida que la entrada se hace más grande. Responde a una sola pregunta: cuando la cantidad de datos se duplica, o crece mil veces, ¿tu código sigue siendo rápido, se ralentiza un poco o se atasca por completo? Ignora deliberadamente los segundos exactos y la velocidad de la máquina, y se centra en la forma del crecimiento, porque eso es lo que decide si un código que funciona con 100 elementos sigue funcionando con 100 millones.
¿Por qué no medir simplemente el tiempo?
Porque los segundos dependen de la máquina, el lenguaje, el compilador y de qué más se esté ejecutando. Ejecuta el mismo código en un portátil y en un servidor y obtendrás números diferentes. Big O descarta todo eso y mide algo más duradero: cómo escala el trabajo con el tamaño de la entrada, normalmente llamado n. Dos algoritmos pueden tardar ambos "unos pocos milisegundos" con una entrada pequeña, y sin embargo uno se mantiene rápido a gran escala mientras que el otro se vuelve inutilizable. Big O es como los distinguimos antes de chocar contra ese muro.
Las complejidades habituales, de la mejor a la peor
Estas son las tasas de crecimiento que te encontrarás con más frecuencia, desde la que escala más rápido hasta la más peligrosa:
| Notación | Nombre | Idea general |
|---|---|---|
| O(1) | Constante | El mismo trabajo sin importar el tamaño de la entrada, p. ej. leer array[5]. |
| O(log n) | Logarítmica | Reduce el problema a la mitad en cada paso, p. ej. la búsqueda binaria. |
| O(n) | Lineal | El trabajo crece al ritmo de la entrada, p. ej. recorrer una lista una vez. |
| O(n log n) | Linearítmica | Lo mejor que puedes lograr para una ordenación general, p. ej. mergesort. |
| O(n²) | Cuadrática | Un bucle dentro de un bucle: bien para 100 elementos, doloroso para un millón. |
| O(2ⁿ) | Exponencial | Se duplica con cada elemento añadido: solo usable para entradas diminutas. |
| O(n!) | Factorial | Cada ordenación posible de la entrada: práctica solo para n muy pequeña. |
Por qué se descartan las constantes y los términos pequeños
A Big O le importa el crecimiento, no los recuentos exactos, así que simplifica. Si un algoritmo realiza 2n + 3 pasos, eso se escribe O(n): el 2 y el 3 no cambian la forma de la curva a medida que n se hace grande. Del mismo modo, n² + n se convierte en O(n²), porque el término cuadrático domina una vez que n es grande. Por eso Big O trata del término dominante, la parte que decide el comportamiento a gran escala, y no de una lectura precisa de cronómetro.
Un ejemplo concreto
Supongamos que quieres comprobar si una lista contiene un duplicado. Un enfoque compara cada elemento con todos los demás: dos bucles anidados, aproximadamente n × n comparaciones, así que O(n²). Otro enfoque añade cada elemento a un hash set y comprueba la pertenencia sobre la marcha: una sola pasada, así que O(n). Con 1.000 elementos la versión cuadrática hace alrededor de un millón de comparaciones; con 100.000 elementos hace diez mil millones, mientras que la versión lineal hace 100.000. La misma tarea, un destino radicalmente distinto a gran escala. Esa diferencia es exactamente lo que Big O está diseñado para revelar.
Peor caso, caso promedio y mejor caso
En sentido estricto, Big O describe una cota superior: normalmente el peor caso, el máximo trabajo que el algoritmo podría hacer. También verás dos parientes: Big Omega (Ω) para el mejor caso, una cota inferior, y Big Theta (Θ) cuando el mejor y el peor caso crecen al mismo ritmo, dando una cota ajustada. En el uso cotidiano la gente dice "Big O" de forma laxa para referirse al crecimiento en el peor caso, porque eso es en torno a lo que planificas: quieres saber lo malo que puede llegar a ser, no lo afortunado que podrías ser de vez en cuando.
La complejidad espacial, también
La misma notación describe la memoria, no solo el tiempo. Un algoritmo que copia toda la entrada a una nueva estructura usa O(n) de espacio extra; uno que reordena la entrada in situ usa O(1) de espacio extra. Con grandes volúmenes de datos, la memoria puede ser el límite real, así que merece la pena preguntarse tanto "¿cómo crece el tiempo?" como "¿cómo crece la memoria?".
Cómo razonar sobre tu propio código
- Cuenta los bucles sobre la entrada. Una sola pasada suele ser O(n); un bucle dentro de un bucle sobre los mismos datos suele ser O(n²).
- Dividir a la mitad es un logaritmo. Si cada paso descarta la mitad de los datos restantes (como la búsqueda binaria), eso es O(log n).
- Las búsquedas en un hash map/set son ~O(1). Sustituir un recorrido anidado por una búsqueda en un hash es la forma clásica de convertir O(n²) en O(n).
- Descarta las constantes. Tres pasadas simples separadas siguen siendo O(n), no O(3n): lo que importa es la forma.
Preguntas frecuentes
¿Un Big O más bajo siempre es más rápido? A gran escala, sí, pero no siempre para entradas pequeñas. Las constantes y la sobrecarga que Big O ignora pueden hacer que un método O(n²) supere a uno O(n log n) con un puñado de elementos. Big O te dice quién gana a medida que crecen los datos, que suele ser lo que importa.
¿Cuál es la mejor complejidad posible? O(1), tiempo constante: el trabajo no crece con la entrada en absoluto. La siguiente mejor es O(log n). Para los problemas que deben mirar cada elemento al menos una vez, O(n) es el mínimo.
¿Por qué O(n log n) es especial para ordenar? Es la cota inferior demostrada para la ordenación general basada en comparaciones, así que mergesort, heapsort y las buenas implementaciones de quicksort apuntan todas a ella. En general no se pueden ordenar datos arbitrarios más rápido solo mediante comparaciones.
¿Necesito Big O para programar a diario? No necesitas las matemáticas formales, pero la intuición es de un valor incalculable: reconocer cuándo un bucle anidado va a explotar con una entrada grande, o cuándo una búsqueda en un hash te salva, evita clases enteras de errores de rendimiento.