La regla que mide la velocidad

Cuenta los pasos

Los segundos confunden.
En una computadora rápida
hasta una forma lenta se ve veloz.
Por eso, en vez de segundos,
contamos "¿cuántos pasos?"
Cuando hay n casillas,
cada forma
da un número distinto de pasos.

Elige un tamaño de entrada y cuenta los pasos de cada forma. (Uno por uno = n · por mitades = pocos)

Con pocas casillas,
las dos se parecen.
Con 8 casillas,
uno por uno son 8,
por mitades son 3.
Poca diferencia.
¿Pero qué pasa
si crecemos mucho las casillas?

Qué pasa al crecer

Aquí se ve la verdad.
Haz crecer n, y
una forma sube
despacio, con las casillas,
mientras otra,
cuando las casillas se duplican,
salta a cuatro veces el trabajo.
n por n,
eso es n al cuadrado.

Toca para crecer n. n sube con las casillas, pero n al cuadrado explota a medida que las casillas crecen.

n al cuadrado da miedo
cuando las casillas son grandes.
100 casillas:
n es 100,
n al cuadrado es 10.000.
1.000 casillas:
n es 1.000,
n al cuadrado es un millón.
Empieza pequeño
pero pronto crece sin control.

Compara las curvas

Pon tres crecimientos
uno al lado del otro
y lo ves de un vistazo.
log n
apenas sube
aunque crezcan las casillas.
n sube en línea inclinada,
n al cuadrado se curva hacia arriba
y se dispara muy alto.

Toca para encender curvas y comparar. En el mismo n, log n, n y n al cuadrado alcanzan alturas completamente distintas.

Ahora ves
por qué cortar a la mitad
era tan rápido.
Por mitades es log n:
hasta mil casillas
terminan en unas diez.
Uno por uno es n:
mil significa mil.
La forma del crecimiento
decidió al ganador.

Quédate solo con el término mayor

Cuenta los pasos reales y
sale una fórmula enredada
como 3n al cuadrado + 5n + 9.
Pero cuando n se hace muy grande,
n al cuadrado
aplasta al resto.
Por eso borramos los términos pequeños
y dejamos solo
el que más crece, n al cuadrado.

Toca los términos pequeños para borrarlos uno a uno. En 3n al cuadrado + 5n + 9, cuando n es grande solo queda n al cuadrado, y eso es la O grande.

Quitamos también el número de adelante.
3n al cuadrado o 100n al cuadrado,
la forma del crecimiento es el mismo n al cuadrado.
Así que solo escribimos
O(n al cuadrado).
La O grande es una etiqueta
que escribe, en una línea,
"¿en qué forma crece para entradas grandes?"

Mira hasta dónde llegamos

En resumen:
la velocidad no se mide en segundos
sino por la forma del crecimiento.
A medida que las casillas n crecen,
log n apenas sube,
n sube con las casillas,
n al cuadrado explota.
Por enredada que esté la fórmula,
miras solo el término mayor,
y esa marca es la O grande.

Toca las tres para resumir en una línea. log n casi plana, n inclinada, n al cuadrado estallando hacia arriba. Solo mira el término mayor.

Ahora, al mirar un método,
puedes calcular su velocidad
sin cronometrar un segundo.
Si al duplicar las casillas
se duplica el trabajo, bien;
si salta a cuatro veces, cuidado.
Un buen método
es el que crece despacio
incluso ante un trabajo grande.