Notación Big O
Una forma abreviada de decir cuánto crece el trabajo de un algoritmo con más datos.
La notación Big O (o notación O grande) describe cómo crece el tiempo (o la memoria) que usa un algoritmo a medida que crece la cantidad de datos, sin importar los detalles de una computadora en particular. No dice "esto tarda 2 segundos"; dice "si duplicás los datos, tarda más o menos el doble" o "cuatro veces más". Se escribe O(n), O(n²) y así, donde n es el tamaño de la entrada.
Unas pocas clases cubren casi todos los casos cotidianos. O(1), constante: leer el elemento 500 de un arreglo, o buscar una clave en una tabla hash, tarda más o menos lo mismo haya los datos que haya. O(log n), logarítmica: la búsqueda binaria en una lista ordenada de un millón de elementos necesita unas 20 comparaciones, porque cada paso descarta la mitad. O(n), lineal: revisar cada elemento una vez. O(n log n): los buenos métodos de ordenamiento de uso general. O(n²), cuadrática: comparar cada elemento con todos los demás, bien para cien, un sufrimiento para un millón.
La notación describe el peor caso y se queda solo con la parte que domina cuando n se hace grande, así que 3n + 50 es simplemente O(n). Por eso importa en la práctica: un pedazo de código cuadrático que andaba al instante en las pruebas con 1.000 filas puede tumbar un servicio en producción con 1.000.000, porque el trabajo se multiplicó por un millón y no por mil. Los ingenieros usan Big O para comparar enfoques antes de escribirlos y para explicar por qué algo se puso lento.
Para quedarse
- Describe cómo crece el trabajo con los datos, no los segundos exactos.
- Clases comunes: O(1), O(log n), O(n), O(n log n), O(n²).
- Solo cuenta el término que domina: 3n + 50 es O(n).
- Explica por qué un código rápido en las pruebas se arrastra a escala real.