Complejidad algorítmica¶

De un vistazo

Materia: Capa 0 · Cimientos · Tiempo de lectura: ~30 min · Requisitos previos: Modelo de ejecución y Estructuras de datos.

En una frase: la complejidad algorítmica es la herramienta para predecir cómo se comporta tu código cuando los datos crecen, sin ejecutarlo y sin depender de tu máquina. Es la diferencia entre "va rápido en mi portátil" y "sé que aguantará en producción con 100× los datos".

Por qué esto importa¶

El error más caro y silencioso de un programador: escribir algo que funciona perfecto en pruebas y se derrite en producción. Con 200 registros de prueba todo va fino; con los 2 millones reales, la misma pantalla tarda 40 segundos o tumba el servidor. No es un bug —el código es "correcto"—, es que escala mal, y eso no se ve mirando si funciona.

La complejidad te da un lenguaje para responder, antes de desplegar:

¿Este código aguantará 10× o 100× los datos, o explota?
Entre dos soluciones que "funcionan", ¿cuál se hunde antes?
¿Por qué añadir un bucle dentro de otro puede pasar de 1 segundo a 3 horas?
¿Merece la pena optimizar esto, o el cuello de botella está en otro sitio?

Sin esto, optimizas por superstición. Con esto, razonas sobre el futuro de tu código y detectas la bomba de relojería antes de que estalle un viernes por la tarde.

Intuición primero: cuenta cómo CRECE el trabajo, no cuánto tarda¶

La tentación es medir en segundos. Mala idea: los segundos dependen de tu CPU, del lenguaje, de la carga del servidor, de la fase de la luna. Un algoritmo lento en un portátil de 2015 puede parecer rápido en un servidor de 2025 y engañarte.

La complejidad hace algo más astuto: ignora la velocidad de la máquina y cuenta cómo crece el número de operaciones a medida que crece la entrada. No pregunta "¿cuánto tarda?", sino "si doblo los datos, ¿qué le pasa al trabajo: se dobla, se cuadruplica, apenas se inmuta?". Esa forma de crecer es propia del algoritmo y no cambia de máquina a máquina.

Una imagen:

Buscar un nombre en una agenda página por página: si la agenda tiene el doble de nombres, tardas el doble. El trabajo crece igual que los datos → lineal.
Buscarlo abriendo por la mitad y descartando media agenda cada vez (está ordenada): doblar los nombres solo añade una apertura más. El trabajo apenas crece → logarítmico.
Comparar a cada persona con todas las demás en una fiesta: si viene el doble de gente, los apretones de manos se cuadruplican. El trabajo crece con el cuadrado → cuadrático.

Esa es toda la idea. Ahora le ponemos nombre y notación.

El detalle¶

1. La notación O grande: quedarse con lo que domina¶

La notación O grande (Big-O) describe cómo crece el número de operaciones en función del tamaño de la entrada, que llamamos n. Su regla es brutalmente simplificadora, y esa es su fuerza:

Ignora las constantes. O(2n) y O(500n) son ambos O(n). Nos da igual el factor: nos importa la forma de la curva, no su inclinación exacta. (Doblar la máquina cambia la constante, no la forma.)
Se queda con el término que manda cuando n es grande. En n² + n + 100, cuando n vale un millón, el n² aplasta a todo lo demás. Se queda O(n²).

O sea: Big-O es un límite superior sobre la forma de crecer, deliberadamente tosco, pensado para el comportamiento a gran escala. No sirve para decir "esto tarda 3,2 ms"; sirve para decir "esto escala como n²", que es la información que evita desastres.

2. Las clases que tienes que reconocer de un vistazo¶

Ordenadas de mejor a peor. Interiorizar esta escalera es el 80% del valor práctico de la lección:

Notación	Nombre	Si doblas `n`, el trabajo…	Ejemplo típico
O(1)	Constante	no cambia	acceso a un array por índice; `isset` en un hash
O(log n)	Logarítmico	sube en 1 escalón	búsqueda binaria; buscar en un árbol/índice
O(n)	Lineal	se dobla	recorrer una lista una vez
O(n log n)	Lineal-logarítmico	algo más que el doble	los buenos ordenamientos (merge sort, quicksort)
O(n²)	Cuadrático	se cuadruplica	dos bucles anidados sobre los mismos datos
O(2ⁿ)	Exponencial	se eleva al cuadrado	probar todas las combinaciones (fuerza bruta)

Para que la escalera deje de ser abstracta, mira lo que significan con n = 1.000.000 de elementos, suponiendo mil millones de operaciones por segundo:

Clase	Operaciones aprox.	Tiempo aprox.
O(log n)	~20	instantáneo
O(n)	1.000.000	~0,001 s
O(n log n)	~20.000.000	~0,02 s
O(n²)	1.000.000.000.000	~17 minutos
O(2ⁿ)	un número con 300.000 cifras	más que la edad del universo

Ahí está el mensaje que salva proyectos: la diferencia entre O(n log n) y O(n²) no es "un poco más lento", es la diferencia entre 0,02 segundos y 17 minutos con los mismos datos. Y O(2ⁿ) es sencillamente inviable salvo para n diminutos.

graph LR
  A["O(1)"] --> B["O(log n)"] --> C["O(n)"] --> D["O(n log n)"] --> E["O(n²)"] --> F["O(2ⁿ)"]
  A -.->|"cada flecha:<br/>escala mucho peor"| F

3. Cómo se cuenta en tu código (sin matemáticas)¶

No necesitas demostraciones; necesitas leer estructura:

Operaciones sueltas (una asignación, una suma, un isset): O(1).
Un bucle sobre n elementos: O(n). Haces trabajo constante n veces.
Un bucle dentro de otro, ambos sobre n: O(n²). Por cada uno de los n, recorres los n. Esta es la que más veces aparece sin querer.
Dividir el problema por la mitad en cada paso: O(log n). (Doblar n solo añade una división más.)
Dividir por la mitad y recorrer en cada nivel: O(n log n). La firma de los buenos ordenamientos.

// O(n): un solo recorrido
foreach ($usuarios as $u) { enviar($u); }

// O(n²): por cada usuario, recorro TODOS los usuarios. Bomba a escala.
foreach ($usuarios as $a) {
    foreach ($usuarios as $b) {
        if ($a->id !== $b->id && $a->email === $b->email) marcarDuplicado($a);
    }
}

Ese O(n²) con 1.000 usuarios son 1.000.000 de comparaciones (va fino). Con 100.000 usuarios son 10.000 millones (se muere). El código es idéntico; solo cambió n. Sabiendo leer la complejidad, ves la bomba sin ejecutarla —y sabes que meter los emails en un hash lo baja a O(n).

4. Mejor, peor y caso promedio¶

Un mismo algoritmo puede tener costes distintos según los datos concretos:

Peor caso: el más desfavorable. Es el que más importa: es la garantía, el "nunca será peor que esto". Cuando alguien dice "O(n)" a secas, casi siempre habla del peor caso.
Caso promedio: lo esperable con datos típicos. Es lo del hash: O(1) promedio, aunque su peor caso sea O(n).
Mejor caso: el más favorable. Suele ser poco útil (nadie diseña para el día de suerte).

La distinción no es pedantería: el hash table es O(1) en promedio pero O(n) en el peor caso, y confiar en el promedio cuando un atacante puede forzar el peor caso es un agujero de seguridad real (hash-flooding, lo vimos en la lección anterior).

5. Complejidad amortizada: el coste caro pero raro¶

Recupera el array dinámico: añadir al final es O(1)… salvo cuando se llena y hay que copiarlo todo, que es O(n). ¿Cómo se describe algo que es casi siempre barato y de vez en cuando caro?

La complejidad amortizada reparte el coste de las operaciones caras y raras entre las muchas baratas. Como duplicar la capacidad hace que las copias sean cada vez más infrecuentes, la suma de copiar al insertar n elementos es proporcional a n, no a n². Repartido, cada inserción sale a O(1) amortizado.

Amortizado ≠ promedio

No es lo mismo. Promedio habla de distintas entradas (unas con suerte, otras no). Amortizado habla de una secuencia de operaciones sobre la misma estructura: garantiza que el coste total de la secuencia es bajo, aunque una operación puntual sea cara. El amortizado es una garantía sobre el conjunto; el promedio, una expectativa estadística.

6. No solo tiempo: la complejidad espacial¶

Todo lo anterior mide operaciones (tiempo). La misma idea se aplica a la memoria: la complejidad espacial describe cuánta memoria extra necesita el algoritmo según n.

Recorrer un array sumando: O(1) en espacio (una variable acumuladora, no importa n).
Construir una copia transformada del array: O(n) en espacio.
Muchas soluciones son un canje tiempo↔espacio: puedes acelerar algo guardando resultados en un hash (más memoria, menos tiempo). Ese canje es una de las decisiones de diseño más habituales. El out of memory de la lección de memoria suele ser una complejidad espacial que no vigilaste.

Cómo se ve en la práctica¶

El caso clásico de "funciona en pruebas, muere en producción":

// Detectar pedidos duplicados por número de factura.
// ❌ O(n²): con 500 pedidos de prueba, 250.000 comparaciones → instantáneo.
//           con 200.000 reales, 40.000 millones → el informe nunca termina.
foreach ($pedidos as $a) {
    foreach ($pedidos as $b) {
        if ($a !== $b && $a->factura === $b->factura) { $dups[] = $a; break; }
    }
}

// ✅ O(n): una pasada, usando un hash para "¿ya vi esta factura?"
$vistas = [];
foreach ($pedidos as $p) {
    if (isset($vistas[$p->factura])) { $dups[] = $p; }
    $vistas[$p->factura] = true;
}

Las dos "funcionan" y pasan los tests con datos pequeños. La primera es una bomba de relojería que nadie ve hasta que los datos crecen; la segunda escala. Distinguirlas es leer la complejidad, no ejecutar el código. Ese es el superpoder que da esta lección.

Lo que sacrificas / errores comunes¶

Optimizar la constante en vez de la clase. Pasar de O(2n) a O(n) (la mitad de tiempo) es ruido comparado con pasar de O(n²) a O(n log n). Ataca primero la forma, no el factor.
Optimizar sin medir dónde está el cuello de botella. Un O(n²) sobre 10 elementos no es tu problema; sobre 10 millones, sí. La complejidad dice qué escalará mal; un profiler dice qué está doliendo ahora. Necesitas los dos.
Olvidar los costes ocultos. in_array dentro de un bucle parece un bucle simple pero es O(n²) camuflado, porque in_array ya es O(n). Muchas funciones de librería esconden su propia complejidad.
Confundir "correcto" con "escalable". Pasar los tests no dice nada sobre la complejidad. Un algoritmo exponencial da resultados correctos… cuando termina.

Resumen¶

La complejidad mide cómo crece el trabajo cuando crece n, ignorando la velocidad de la máquina. Responde "¿aguantará a escala?", no "¿cuántos ms tarda?".
Big-O ignora constantes y se queda con el término dominante: describe la forma de crecer.
Memoriza la escalera: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ). El salto de O(n log n) a O(n²) es la frontera entre "escala" y "se muere".
Distingue peor / promedio / amortizado: el hash es O(1) promedio pero O(n) peor caso; el append del array dinámico es O(1) amortizado.
Existe también la complejidad espacial (memoria), y muchas optimizaciones son un canje tiempo↔espacio.

Ejercicios socráticos¶

Razónalos. La respuesta está en la lección.

Un algoritmo hace exactamente 3n² + 1000n + 50000 operaciones. ¿Cuál es su Big-O y por qué desaparecen el 3, el 1000n y el 50000? ¿A partir de qué escala empieza a dominar el término cuadrático sobre el 1000n?
Tienes código O(n²) que tarda 1 segundo con 10.000 elementos. Sin cambiar nada, ¿cuánto tardará (en orden de magnitud) con 100.000? ¿Y si fuera O(n)? ¿Y O(n log n)?
El acceso a un hash table es O(1) promedio pero O(n) en el peor caso. Describe un escenario en el que ese peor caso ocurra de verdad, y por qué apoyarte en el promedio podría ser un problema de seguridad.
Explica con tus palabras por qué añadir a un array dinámico es O(1) amortizado aunque algunas inserciones concretas sean O(n). ¿En qué se diferencia de decir que es O(1) promedio?
Te dan dos funciones que producen el mismo resultado: una O(n) que construye un hash auxiliar (O(n) de memoria) y otra O(n²) que no usa memoria extra (O(1) de espacio). ¿Cuál eliges y de qué depende tu respuesta? Nombra el canje que estás haciendo.

Repaso espaciado¶

A Anki (repasos.md).

[ ] ¿Por qué Big-O ignora las constantes y los términos no dominantes? ¿Qué información busca capturar?
[ ] Ordena de mejor a peor: O(n²), O(1), O(n log n), O(log n), O(n), O(2ⁿ). Di qué le pasa a cada una al doblar n.
[ ] ¿Por qué dos bucles anidados sobre los mismos n datos son O(n²)? Da un ejemplo y cómo bajarlo a O(n).
[ ] Diferencia peor caso, caso promedio y complejidad amortizada con un ejemplo de cada uno.
[ ] ¿Qué es la complejidad espacial y qué significa "canjear tiempo por espacio"?

Para seguir tirando del hilo¶

Grokking Algorithms (Bhargava), capítulos de Big-O y búsqueda binaria — la introducción más amable.
Introduction to Algorithms (CLRS) — la referencia rigurosa, para cuando quieras las demostraciones (análisis amortizado incluido).
Experimento: implementa el detector de duplicados en sus versiones O(n²) y O(n), y cronométralas con 1.000, 10.000 y 100.000 elementos. Ver la curva cuadrática dispararse asienta la escalera para siempre.