Crecimiento Big-O: cuánto cuesta de verdad cada clase de complejidad
Tus datos
Dos algoritmos frente a frente
La constante es todo lo que la notación tira: asignaciones, fallos de caché, el trabajo dentro de cada paso. Dale a un algoritmo una constante más pesada y mira dónde deja de importar.
Esta página no lee tu bucle. Adivinar la complejidad leyendo código sería una conjetura vestida de medición: un bucle puede cortarse antes, una sola llamada dentro puede esconder el costo real, y la recursión casi nunca se lee por lo que hace. Tú eliges la clase; lo que la página calcula a partir de ahí es exacto.
Resultados
| Dónde uno adelanta al otro, en elementos | — |
| Operaciones de cada uno, en el tamaño de arriba | — |
Con las cifras con que empieza esta página, el cruce queda en 439 elementos. Quien cambia por la clase mejor en una lista de doscientos dejó el programa más lento y el código más difícil, y la notación no avisó, porque la notación habla de lo que pasa a la larga, no de lo que te pasa a ti.
Cada clase en este tamaño
| Clase | Operaciones | Tiempo | Multiplicado por, si la entrada se duplica |
|---|
La última columna es la que vale la pena mirar fijo, porque es la columna que nadie lleva en la cabeza. El trabajo lineal se duplica. El cuadrático se cuadruplica. El exponencial se eleva al cuadrado: con mil elementos ya en juego, duplicar la entrada multiplica el costo por dos elevado a mil, un número de trescientos dos dígitos.
El factorial es peor de un modo que no tiene nada que ver con duplicar. Agregar un solo elemento multiplica el costo por la cuenta nueva, así que el vigésimo primer elemento cuesta veintiuna veces el problema entero de veinte. Por eso un viajante exacto con veinte ciudades son 2,4 millones de millones de millones de pasos, o setenta y siete años a mil millones por segundo, mientras que esas mismas veinte ciudades bajo dos elevado a n terminan en una milésima de segundo.
Eso también explica por qué la distancia entre clases es aburrida en tamaños pequeños y brutal en grandes. En diez elementos, n log n y n al cuadrado están a tres veces uno de otro, algo que ningún usuario notaría. En mil elementos están a cien veces, y en un millón a cincuenta mil veces. Los mismos dos algoritmos, el mismo código, nada cambió salvo la entrada.
O sea: la lectura honesta de una clase de complejidad es una promesa sobre la forma de la curva, no sobre la velocidad. Dice cómo reacciona el costo cuando la entrada crece, y no dice nada en absoluto sobre si es rápido hoy, en tu máquina, en el tamaño que de verdad tienes.
¿Una clase de complejidad mejor significa un programa más rápido?
En tu tamaño, no necesariamente. La clase describe cómo reacciona el costo cuando la entrada crece; no dice nada sobre el trabajo dentro de cada paso, y ese trabajo es justo lo que la notación tira.
Con las cifras con que empieza esta página, el algoritmo cuadrático de constante ligera le gana al n log n con constante cincuenta en toda entrada por debajo de 439 elementos. Por encima, la clase mejor se dispara y ya no devuelve la delantera.
¿Por qué esta página no lee mi código?
Porque adivinar la complejidad a partir del código fuente es una conjetura vestida de medición. Un bucle puede cortarse antes, una llamada dentro puede esconder el costo real, y la recursión casi nunca se lee por lo que hace.
Así que aquí la clase es una entrada tuya, no una opinión de la página. Todo lo que se calcula a partir de ella es aritmética exacta, y nada en la página finge saber qué hace tu bucle.
¿Qué pasa realmente cuando la entrada se duplica?
El trabajo lineal se duplica y el cuadrático se cuadruplica, y casi todo el mundo lo lleva en la cabeza. El exponencial se eleva al cuadrado, y eso casi nadie lo lleva: en mil elementos, duplicar la entrada multiplica el costo por dos elevado a mil.
El factorial ni siquiera funciona así. Agregar un solo elemento multiplica el costo por la cuenta nueva, así que el vigésimo primer elemento cuesta veintiuna veces el problema entero de veinte.
| Clase | Multiplicado por cuando la entrada se duplica, en mil elementos |
|---|---|
| O(n) | 2 |
| O(n log n) | 2,2 |
| O(n²) | 4 |
| O(n³) | 8 |
| O(2ⁿ) | 1,07 x 10^301 |
¿Por qué un viajante de comercio exacto es imposible con veinte ciudades?
Porque veinte factorial son 2,4 millones de millones de millones de pasos, que a mil millones de operaciones por segundo son setenta y siete años. Esos mismos veinte elementos bajo dos elevado a n tardan cerca de una milésima de segundo.
Esa es la diferencia práctica entre exponencial y factorial, y por eso vale la pena separarlos en vez de archivar ambos como imposible.
Reacciones
0
0 Comentarios
Se el primero en comentar