ENES

Notación Big O

Una forma abreviada de decir cuánto crece el trabajo de un algoritmo con más datos.

Un gráfico de trabajo según el tamaño de la entrada con cuatro curvas: plana O(1), que sube despacio O(log n), recta O(n) y que se dispara O(n²)

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

Para seguir leyendo

Términos relacionados

Más de Software