¿Qué tan rápido? La notación O grande

A mil millones de pasos por segundo, un método n² con un millón de valores tarda unos 17 minutos; un método n log n tarda 0.02 segundos.

El crecimiento importa más que el conteo exacto

Hasta ahora hemos contado los pasos con exactitud: 45 comparaciones, 4 intercambios, 20 comprobaciones. Los conteos exactos sirven para ejemplos pequeños, pero dependen de detalles como si el ordenamiento de burbuja termina antes o cómo se elige un pivote. Cuando la entrada se hace grande, hay algo que domina todo lo demás: cómo crece el conteo a medida que crece n. Un algoritmo cuyos pasos crecen como n² terminará perdiendo contra uno cuyos pasos crecen como n log n, por muy bien ajustado que esté el primero.

La notación O grande es la forma abreviada de expresar ese crecimiento. Escribir que un algoritmo es O(n²), que se lee "O grande de n al cuadrado", significa que para n grande su número de pasos es como máximo una constante por n². Dos reglas lo hacen fácil de usar. Se eliminan los factores constantes: 3n y n/2 son los dos O(n). Se conserva solo el término que crece más rápido: n²/2 − n/2, las comparaciones del ordenamiento por selección, es O(n²), porque para n grande la parte n² es casi todo. El curso 6.006 del MIT usa la misma idea cuando compara estructuras de datos y ordenamientos por su tiempo de ejecución asintótico.

Las tasas de crecimiento más comunes

• O(1), constante. El trabajo no depende de n: leer el primer valor de una lista, o un valor en una posición conocida.
• O(log n), logarítmica. Cada paso parte el problema por la mitad: la búsqueda binaria. Un millón de valores, unos 20 pasos.
• O(n), lineal. Cada valor se trata una vez: la búsqueda lineal, encontrar el valor más grande, sumar una lista.
• O(n log n). El ordenamiento por mezcla, y el quicksort en promedio. Lo mejor que puede hacer un ordenamiento por comparación.
• O(n²), cuadrática. Se mira cada par: los ordenamientos de burbuja, selección e inserción en el peor caso, o dos bucles anidados uno dentro de otro.
• O(2ⁿ), exponencial. El trabajo se duplica con cada valor extra: probar todos los subconjuntos de n elementos, o mover n discos en la Torre de Hanói.

Qué significan las cifras en segundos

Supón que una computadora hace mil millones (10⁹) de pasos básicos por segundo, una cifra redonda razonable para un núcleo de procesador. Esto es lo que significa cada tasa de crecimiento para un millón de valores. O(log n) son unos 20 pasos, muy por debajo de un microsegundo. O(n) es un millón de pasos, un milisegundo. O(n log n) son unos 20 millones de pasos, 0.02 segundos. O(n²) son 10¹² pasos, mil segundos, unos 17 minutos. O(2ⁿ) no se puede terminar: 2 elevado a un millón es un número de más de 300 000 dígitos. Por eso elegir el algoritmo correcto suele importar mucho más que comprar una computadora más rápida. Una máquina diez veces más rápida convierte 17 minutos en 1.7 minutos; pasar de O(n²) a O(n log n) los convierte en una cincuentava parte de segundo.

Leer la O grande en el código

Muchas veces puedes leer la tasa de crecimiento directamente en la forma del código. Un solo bucle sobre la lista es O(n). Dos bucles, uno dentro del otro, ambos sobre la lista, son O(n²): por cada una de las n vueltas del bucle exterior, el interior da hasta n vueltas. Un bucle que parte un número por la mitad cada vez, como while (n > 1) n = Math.floor(n / 2), es O(log n): empezando en 1000 se ejecuta 9 veces, y empezando en un millón, 19. Los pasos que ocurren uno tras otro se suman, y gana el término mayor: un bucle O(n) seguido de un bucle O(n²) es O(n²) en total.

// O(n): una pasada
let total = 0;
for (const x of list) total += x;

// O(n²): todos los pares
for (let i = 0; i < list.length; i++)
  for (let j = i + 1; j < list.length; j++)
    if (list[i] === list[j]) console.log("duplicate", list[i]);

// O(log n): partir por la mitad
let k = list.length, rounds = 0;
while (k > 1) { k = Math.floor(k / 2); rounds++; }

Mejor caso, caso promedio y peor caso

Un mismo algoritmo puede comportarse de forma muy distinta con entradas distintas. El ordenamiento por inserción es O(n) con una lista que ya está ordenada y O(n²) con una invertida. El quicksort es O(n log n) en promedio y O(n²) con pivotes malos de forma sistemática. Cuando alguien da una sola cifra de O grande sin decir de qué caso, normalmente se refiere al peor caso, porque es una garantía: el algoritmo nunca lo hará peor. La O grande también deja cosas fuera. Ignora los factores constantes, así que con entradas pequeñas un método O(n²) de pasos muy simples puede ganarle a uno O(n log n). Por eso muchas rutinas de ordenamiento reales pasan al ordenamiento por inserción para los trozos cortos de la lista.