Tasas de Crecimiento, No Costos Absolutos
Big O: Medir Cómo Crecen los Costos
La notación Big O mide la tasa de crecimiento del costo del algoritmo, no el costo absoluto.
La pregunta que Big O responde: si el tamaño del input N se duplica, el trabajo se duplica, se cuadruplica o se mantiene plano?
La 'O' significa 'orden de magnitud'. La expresión dentro del paréntesis describe la forma de la curva de crecimiento.
Clases de complejidad clave:
- O(1) — constante: el costo no crece. Ejemplo: buscar un valor por índice en un array. Ya que el array tenga 10 elementos o 10 millones, una búsqueda sigue siendo una búsqueda.
- O(N) — lineal: el costo crece con el input. Ejemplo: leer cada elemento en una lista una vez. Duplicar la lista, duplicar las lecturas.
- O(N²) — cuadrática: el costo crece al cuadrado del input. Ejemplo: comparar cada elemento con todos los demás elementos. Duplicar N, cuadruplicar el trabajo.
Tabla de comparación de crecimiento:
| N | O(1) | O(N) | O(N²) |
|---|------|------|-------|
| 10 | 1 | 10 | 100 |
| 100 | 1 | 100 | 10,000 |
| 1,000 | 1 | 1,000 | 1,000,000 |
A N=10 la diferencia parece pequeña. A N=1,000 el vacío se vuelve enorme.
Comparar O(N) con O(N²)
Utilice la tabla de comparación de crecimiento anterior.
A N=1,000: O(N) requiere 1,000 operaciones. O(N²) requiere 1,000,000 operaciones.
Cómo la Estructura del Código Revela la Complejidad
Cómo Identificar Big O a Partir del Código
Big O se esconde en la forma de tu código. Cuatro patrones cubren la mayoría de los casos:
Bucle único sobre N elementos: O(N)
# O(N): una pasada a través de la lista
for item in list_of_n_items:
process(item)Bucles anidados, cada uno sobre N elementos: O(N²)
# O(N²): cada elemento emparejado con todos los demás elementos
for item_a in list_of_n_items:
for item_b in list_of_n_items:
compare(item_a, item_b)Consulta de tiempo constante: O(1)
Acceso a un índice de array, consulta en una tabla hash — un paso independientemente del tamaño.
Divide y vencerás (corta el problema en la mitad en cada paso): O(log N)
Búsqueda binaria: cada verificación reduce la mitad de los elementos restantes.
---
O(N²) oculto: una lista dentro de un bucle
# Parece O(N) pero en realidad es O(N²)
visited = []
for item in list_of_n_items:
if item not in visited: # escanea todos los elementos de visited: O(N)
visited.append(item) # el bucle entero: O(N²)La línea if item not in visited escanea cada elemento de visited en cada iteración. Escanear una lista cuesta O(N). Un bucle que corre N veces, cada uno haciendo O(N) trabajo: O(N) × O(N) = O(N²).
Este patrón aparece en 1.000+ proyectos de código abierto. La solución requiere un solo carácter: reemplazar visited = [] con visited = set(). La prueba de pertenencia a un conjunto cuesta O(1), no O(N). Un cambio. Mismos resultados. 1.000× más rápido a N=1.000.
Clasificar y Corregir Este Código
Lee este código:
result = []
for name in student_names:
if name not in result:
result.append(name)Teoría y Práctica
Big O en la Vida Real
Big O no es solo teoría. Separa los programas que se ejecutan en segundos de los que tardan 17 minutos - en la misma tarea exacta.
Ejemplo real: detección de ciclos de dependencia en un sistema de compilación.
Cuando instala software, su computadora resuelve un gráfico de dependencias: paquete A necesita B, B necesita C y así sucesivamente. Un sistema de compilación verifica este gráfico para detectar ciclos.
Un algoritmo de detección de ciclos O(N²) funciona bien con N=100 paquetes. Con N=50,000 paquetes (un proyecto real): tarda 17 minutos. La solución O(N): 10 segundos.
Esta misma deficiencia existe en GHC (compilador de Haskell), pip (administrador de paquetes de Python), Maven (sistema de compilación de Java), Cargo (administrador de paquetes de Rust) y en más de 1,000 proyectos.
No porque sus autores fueran descuidados. Se escribió visited = [] cuando N era pequeño. El código se calcificó. N creció. Nadie se dio cuenta hasta que el build tardaba media hora.
Big O es la vocabulario que te permite nombrar lo que sucedió - y arreglarlo.
---
¿Te gustaría profundizar más? Nuestro curso sin Hamming incluye un capítulo completo sobre Big O, MOAD-0001 (una verdadera deficiencia O(N²) encontrada en 1,000+ proyectos de código abierto), y por qué nombrar un patrón te permite encontrarlo en todas partes. Consulta [El Capítulo Faltante: Complejidad Algorítmica](/es/un/unhamming_algorithmic_complexity).
Prediga los Tiempos de Compilación
Un sistema de compilación utiliza detección de ciclos O(N²).
Tiempo de compilación medido:
- N=100 paquetes: 0.01 segundos
- N=1,000 paquetes: 1 segundo
Para O(N²): el tiempo se escala como (N_new / N_old)².
Para O(N): el tiempo se escala como (N_new / N_old).