Comparar complejidades permite elegir algoritmos que sigan siendo viables cuando crecen los datos. La decisión combina el orden de crecimiento, las constantes, el tamaño esperado y los recursos disponibles.
La complejidad resume cómo cambia el costo de un algoritmo cuando aumenta el tamaño de entrada. No reemplaza las mediciones, pero permite anticipar qué solución escalará y cuál se volverá demasiado costosa.
Una buena comparación no se limita a una etiqueta Big-O: debe indicar qué recurso se mide, qué caso se analiza, cuáles son las precondiciones y qué tamaño de datos espera la aplicación.
Las funciones ubicadas más a la izquierda crecen más lentamente. La diferencia entre n y n log n puede ser aceptable; la diferencia entre n² y 2n suele decidir si un problema es viable.
| Complejidad | Patrón | Ejemplo |
|---|---|---|
| Θ(1) | Acceso o cálculo fijo | Acceder a un arreglo por índice |
| Θ(log n) | Reducir por un factor | Búsqueda binaria |
| Θ(n) | Recorrer una vez | Buscar máximo |
| Θ(n log n) | Dividir y combinar | Merge sort |
| Θ(n²) | Comparar pares | Detección ingenua de duplicados |
| Θ(2n) | Explorar subconjuntos | Fuerza bruta |
| Θ(n!) | Explorar permutaciones | Probar todos los órdenes |
| n | log₂ n | n | n log₂ n | n² | 2ⁿ |
|---|---|---|---|---|---|
| 10 | ≈ 3 | 10 | ≈ 33 | 100 | 1 024 |
| 1 000 | ≈ 10 | 1 000 | ≈ 9 966 | 1 000 000 | Inviable |
| 1 000 000 | ≈ 20 | 1 000 000 | ≈ 19 931 569 | 10¹² | Inviable |
Los órdenes exponenciales y factoriales se separan rápidamente del resto. En cambio, duplicar una entrada apenas agrega un paso en un algoritmo logarítmico.
Para tamaños pequeños, una constante grande puede hacer que un algoritmo de mejor orden sea más lento. Por ejemplo, 1000n supera a n² mientras n sea menor que 1000; para entradas mayores, el cuadrático crece mucho más rápido.
function compararCostos(n) {
return {
logaritmico: Math.ceil(Math.log2(n)),
lineal: n,
linealLogaritmico: Math.round(n * Math.log2(n)),
cuadratico: n * n
};
}
console.log(compararCostos(16));
// { logaritmico: 4, lineal: 16, linealLogaritmico: 64, cuadratico: 256 }
console.log(compararCostos(1024));
// { logaritmico: 10, lineal: 1024, linealLogaritmico: 10240, cuadratico: 1048576 }Los valores representan tendencias, no tiempos exactos. Las operaciones reales y el entorno determinan las constantes.
| Condición | Algoritmo | Complejidad |
|---|---|---|
| Arreglo no ordenado | Búsqueda lineal | Θ(n) en peor caso |
| Arreglo ordenado | Búsqueda binaria | Θ(log n) en peor caso |
| Tabla hash bien dimensionada | Búsqueda por clave | Promedio cercano a Θ(1) |
| Árbol balanceado | Búsqueda por clave | Θ(log n) |
La mejora puede requerir ordenar datos o invertir memoria en una estructura auxiliar. Por eso debe compararse el flujo completo y no una operación aislada.
function busquedaLineal(numeros, buscado) {
for (let i = 0; i < numeros.length; i++) {
if (numeros[i] === buscado) return i;
}
return -1;
}
function busquedaBinaria(numeros, buscado) {
let inicio = 0;
let fin = numeros.length - 1;
while (inicio <= fin) {
const centro = Math.floor((inicio + fin) / 2);
if (numeros[centro] === buscado) return centro;
if (buscado < numeros[centro]) fin = centro - 1;
else inicio = centro + 1;
}
return -1;
}
const datos = [2, 5, 8, 11, 16, 21, 29, 34];
console.log(busquedaLineal(datos, 21)); // 5
console.log(busquedaBinaria(datos, 21)); // 5Ambas devuelven el mismo resultado, pero la binaria depende de que el arreglo esté ordenado y descarta la mitad de los candidatos en cada paso.
Si habrá una sola consulta, ordenar un arreglo puede costar más que buscar linealmente. Si habrá muchas, pagar una vez O(n log n) por ordenar puede compensarse con búsquedas O(log n).
| Estrategia | Tiempo de búsqueda | Memoria adicional |
|---|---|---|
| Recorrer arreglo | Θ(n) | Θ(1) |
| Arreglo ordenado | Θ(log n) | Θ(1) para buscar |
| Tabla hash | Promedio cercano a Θ(1) | Θ(n) |
La solución más rápida no siempre es la mejor si la memoria es limitada, si no se puede alterar el orden de datos o si las consultas son escasas.
| Algoritmo | Peor caso | Memoria | Uso típico |
|---|---|---|---|
| Insertion sort | Θ(n²) | Θ(1) | Arreglos pequeños o casi ordenados. |
| Merge sort | Θ(n log n) | Θ(n) | Rendimiento predecible y estable. |
| Heap sort | Θ(n log n) | Θ(1) | Buen peor caso y poco espacio auxiliar. |
Estabilidad, memoria, distribución de los datos y simplicidad pueden justificar una elección distinta aun cuando dos opciones tengan el mismo orden de tiempo.
Una comparación debe usar el mismo caso para todos los algoritmos. Búsqueda lineal tiene mejor caso Θ(1) y peor Θ(n); búsqueda binaria ordenada tiene peor Θ(log n); merge sort es Θ(n log n) en los casos habituales.
El análisis amortizado estudia una secuencia de operaciones. Por ejemplo, un arreglo dinámico puede copiar n elementos al ampliar capacidad, pero sobre muchas inserciones al final el costo amortizado por inserción es Θ(1).
No todos los problemas dependen de una única n. Un recorrido de matriz es Θ(rc) para r filas y c columnas, y un recorrido de grafo típico es Θ(V + E). Reemplazar todo por n puede ocultar la estructura relevante.
Big-O no contempla directamente caché, red, disco, paralelismo, asignación de memoria ni optimizaciones del motor. Por eso conviene combinar análisis y medición con entradas representativas.
function contarHasta(n) {
let contador = 0;
for (let i = 0; i < n; i++) contador++;
return contador;
}
console.log(contarHasta(10)); // 10
console.log(contarHasta(1000)); // 1000El conteo confirma crecimiento lineal de la operación principal. Medir el tiempo real aportaría información sobre sus constantes.
La complejidad orienta la decisión; el contexto del producto determina cuál de los compromisos es aceptable.
Comparar complejidades permite elegir soluciones que continúen funcionando al crecer los datos. La mejor alternativa equilibra orden de crecimiento, memoria, frecuencia de uso, requisitos de corrección y datos reales.
En el próximo tema estudiaremos las funciones piso y techo, herramientas discretas útiles para expresar redondeos, divisiones enteras y límites de algoritmos.