El crecimiento de una función indica cómo aumenta su valor cuando crece la entrada. En análisis de algoritmos importa más esa tendencia que el tiempo exacto de una ejecución aislada.
Dos algoritmos pueden tardar casi lo mismo con una entrada pequeña y comportarse de manera completamente diferente con millones de datos. El análisis de crecimiento estudia qué ocurre cuando n aumenta sin límite.
Una función de costo T(n) puede contar comparaciones, operaciones, memoria o llamadas. Comparar sus tasas de crecimiento permite anticipar qué soluciones escalan mejor antes de ejecutarlas en producción.
Una función de crecimiento debe indicar respecto de qué tamaño se mide. Para un arreglo, n puede ser su longitud; para un grafo, pueden ser V vértices y E aristas; para un número entero, puede ser la cantidad de bits de su representación.
El conteo exacto puede dar expresiones como T(n) = 3n² + 7n + 12. En análisis asintótico nos concentramos en el comportamiento para n grande: el término 3n² domina a los términos lineales y constantes.
Esto no significa que las constantes sean irrelevantes en la práctica. Significa que, para comparar escalabilidad, el tipo de crecimiento suele ser el factor decisivo.
Una función constante no depende del tamaño de entrada. Un algoritmo puede ejecutar una cantidad fija de operaciones sin importar si recibe 10 o 10 millones de elementos.
Una operación constante dentro de un bucle deja de ser constante en total: si se repite n veces, el costo total pasa a ser lineal.
Una función logarítmica crece muy lentamente. Aparece cuando cada paso reduce el tamaño del problema por un factor constante, por ejemplo al dividir por dos.
La base del logaritmo cambia solo por un factor constante. En análisis asintótico, log2(n), log10(n) y ln(n) pertenecen a la misma clase de crecimiento.
function pasosParaReducirAMitad(n) {
let pasos = 0;
while (n > 1) {
n = Math.floor(n / 2);
pasos++;
}
return pasos;
}
console.log(pasosParaReducirAMitad(16)); // 4
console.log(pasosParaReducirAMitad(1024)); // 10El algoritmo no calcula exactamente un logaritmo real, pero cuenta el mismo fenómeno: cuántas divisiones por dos hacen falta para llegar al caso base.
Una función lineal es proporcional a n. Si duplicamos la entrada, aproximadamente duplicamos el trabajo. Recorrer todos los elementos de un arreglo una vez es el ejemplo más común.
Los algoritmos lineales suelen escalar bien. Aun así, con datos muy grandes o trabajo costoso por elemento, pueden requerir optimización.
La función n log n aparece cuando se realizan aproximadamente log n niveles de trabajo y cada nivel procesa n elementos. Es típica de algoritmos eficientes de ordenamiento por comparación, como merge sort.
En muchos problemas de ordenamiento, n log n es una barrera fundamental cuando el algoritmo solo obtiene información comparando elementos.
Una función cuadrática n² aparece al considerar todos los pares de una colección de n elementos. Más generalmente, las funciones nk con k constante se llaman polinómicas.
| Función | Interpretación frecuente |
|---|---|
| n² | Todos los pares de elementos. |
| n³ | Tres bucles independientes o triples de elementos. |
| nk | k niveles de combinaciones independientes. |
Para n pequeño, un algoritmo cuadrático puede ser aceptable y más simple. El problema aparece cuando n crece: cuadruplicar n multiplica aproximadamente por dieciséis el trabajo de n².
function costos(n) {
return {
lineal: n,
cuadratico: n * n,
linealLogaritmico: Math.round(n * Math.log2(n))
};
}
console.log(costos(10)); // { lineal: 10, cuadratico: 100, linealLogaritmico: 33 }
console.log(costos(1000)); // { lineal: 1000, cuadratico: 1000000, linealLogaritmico: 9966 }Los valores no representan tiempos exactos, sino la magnitud relativa de las funciones. La distancia entre n² y n log n aumenta rápidamente.
Una función exponencial tiene la variable en el exponente, como 2n o 3n. Cada incremento de n multiplica el valor por una constante; por eso crece mucho más rápido que cualquier polinomio.
La fuerza bruta que revisa todos los subconjuntos de n elementos tiene 2n posibilidades. Los algoritmos recursivos sin memoización, como Fibonacci directo, pueden tener este crecimiento.
La función factorial n! = n(n - 1)...1 crece incluso más rápido que una exponencial de base fija. Aparece al considerar todas las permutaciones de n elementos.
Los problemas factoriales exigen podas, heurísticas, programación dinámica u otros métodos para ser tratables con entradas moderadas.
La jerarquía ayuda a priorizar algoritmos. Un algoritmo Θ(n log n) suele ser una mejora sustancial sobre uno Θ(n²), mientras que pasar de Θ(2n) a Θ(n²) puede transformar un problema impracticable en uno resoluble.
| n | log₂ n | n | n log₂ n | n² | 2ⁿ |
|---|---|---|---|---|---|
| 10 | ≈ 3,3 | 10 | ≈ 33 | 100 | 1 024 |
| 20 | ≈ 4,3 | 20 | ≈ 86 | 400 | 1 048 576 |
| 30 | ≈ 4,9 | 30 | ≈ 147 | 900 | 1 073 741 824 |
Incluso con valores pequeños, la función exponencial se separa rápidamente de las demás. La diferencia se vuelve extrema al aumentar n.
Algunas diferencias que parecen pequeñas cambian la clase de crecimiento. Por ejemplo, n² y (n + 1)² pertenecen al mismo orden, pero n² y 2n no.
| Funciones | Relación de crecimiento | Motivo |
|---|---|---|
| n y 7n + 10 | Mismo orden | Difieren por constante y término menor. |
| n² y n² + 100n | Mismo orden | Domina n². |
| n² y n³ | Órdenes distintos | n³/n² = n crece sin límite. |
| n³ y 2ⁿ | Órdenes distintos | La exponencial supera a todo polinomio. |
El crecimiento asintótico no reemplaza las mediciones, pero orienta qué medir. Un algoritmo O(n²) con una constante pequeña puede superar a uno O(n log n) para entradas diminutas; sin embargo, cuando los datos crecen la tendencia suele imponerse.
La complejidad es una herramienta de diseño, no una excusa para ignorar el contexto de una aplicación.
Las mismas funciones se usan para describir memoria. Un algoritmo que almacena un valor por cada entrada usa memoria lineal; una matriz de n por n usa memoria cuadrática; una llamada recursiva puede sumar espacio de pila.
Un algoritmo con buen tiempo puede ser inviable si su consumo de memoria crece demasiado. La evaluación completa considera ambos recursos.
Comprender las tasas de crecimiento permite anticipar la escalabilidad de un algoritmo. En el próximo tema formalizaremos una cota superior mediante la notación Big-O.