Qué es la notación Big O
¿Cómo saber qué método es más rápido? Medirlo con un cronómetro parece lo obvio, pero en una computadora rápida hasta un método lento parece veloz. La verdadera diferencia se esconde mientras hay pocas casillas y aparece cuando su número se dispara. Por eso medimos la velocidad no en segundos, sino preguntando: cuando crecen las casillas, ¿cuánto crece el trabajo?
Contar pasos, no segundos
Los segundos engañan: en una computadora rápida, hasta un método lento parece veloz.
Por eso, en lugar de segundos, contamos cuántos pasos hace falta dar.
Con n casillas, cada método da un número distinto de pasos.
Elige un tamaño de entrada para ver cuántos pasos da cada método. (uno por uno = n pasos · por mitades = muchos menos)
Con pocas casillas, los dos se parecen.
Con 8 casillas, uno por uno da 8 pasos y por mitades da 3, así que la diferencia es pequeña.
Pero ¿qué pasa si las casillas crecen mucho?
Qué pasa cuando n crece
Aquí se ve la verdadera diferencia.
Al hacer crecer n, el trabajo de un método aumenta solo al ritmo de las casillas, mientras que el de otro se multiplica por cuatro cada vez que las casillas se duplican.
n por n se escribe n².
Cada vez que pulsas el botón, las casillas se duplican. n crece con las casillas, pero n² se dispara cada vez más rápido.
n² da miedo cuando hay muchas casillas.
Con 100 casillas, n es 100 y n² es 10 000. Con 1000 casillas, n es 1000 y n² es un millón.
Empieza pequeño, pero enseguida se va de las manos.
Comparar las curvas
Pon los tres crecimientos uno al lado del otro y lo verás de un vistazo.
log n apenas sube, por muchas casillas que haya.
n sube en línea recta e inclinada, y n² se curva hacia arriba y se dispara muy por encima.
Enciende las curvas una a una y compáralas. Con el mismo n, log n, n y n² alcanzan alturas muy distintas.
Ahora queda claro por qué cortar por la mitad era tan rápido.
Por mitades es log n: aunque haya mil casillas, termina en unos diez pasos. Uno por uno es n: mil casillas son mil pasos.
Lo que decidió al ganador fue la forma del crecimiento.
Quedarse solo con el término mayor
Si cuentas los pasos reales, suele salir una fórmula enredada como 3n² + 5n + 9.
Pero cuando n se hace muy grande, n² aplasta a todo lo demás.
Por eso borramos los términos pequeños y nos quedamos solo con el que crece más rápido, n².
Cada pulsación borra un término pequeño o el número de delante. En 3n² + 5n + 9, con n grande solo queda n², y la marca que anota esa forma es la O grande.
También quitamos el número de delante: sea 3n² o 100n², la forma del crecimiento sigue siendo n².
Así que escribimos simplemente O(n²).
La O grande es una etiqueta que dice en una línea cómo crece algo cuando la entrada es grande.
Hasta dónde hemos llegado
En resumen, la velocidad no se mide en segundos sino por la forma del crecimiento.
Cuando n crece, log n apenas sube, n sube con las casillas y n² explota.
Por enredada que sea la fórmula, basta con mirar el término mayor, y la marca que lo indica es la O grande.
Enciende los tres términos uno a uno para resumirlo en una línea. log n queda casi plano, n sube en diagonal, n² explota. Solo importa el término mayor.
Ahora, al ver un método, puedes saber si es rápido sin cronometrarlo.
Si al duplicar las casillas el trabajo también se duplica, vas bien; si se cuadruplica, cuidado.
Un buen método es el que crece despacio incluso ante un trabajo enorme.