Tasas de Crecimiento, No Costos Absolutos
Big O: Midiendo Qué Tan Rápido Crecen Los Costos
La notación Big O mide la tasa de crecimiento del costo de un algoritmo — no el costo absoluto.
La pregunta que Big O responde: conforme el tamaño de entrada N se duplica, ¿se duplica el trabajo? ¿Se cuadruplica? ¿Se queda igual?
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 una matriz. Ya sea que la matriz tenga 10 elementos o 10 millones, una búsqueda sigue siendo una búsqueda.
- O(N) — lineal: el costo crece con la entrada. Ejemplo: leer cada elemento en una lista una vez. Duplica la lista, duplica las lecturas.
- O(N²) — cuadrático: el costo crece como el cuadrado de la entrada. Ejemplo: comparar cada elemento con todos los demás. Duplica N, cuadriplica 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 |
En N=10 la diferencia se ve pequeña. En N=1.000 la brecha se vuelve enorme.
Comparar O(N) con O(N²)
Usa la tabla de comparación de crecimiento anterior.
En N=1.000: O(N) requiere 1.000 operaciones. O(N²) requiere 1.000.000 de operaciones.
Cómo la Estructura del Código Revela la Complejidad
Cómo Identificar Big O en el Código
Big O se esconde en la forma de tu código. Cuatro patrones cubren la mayoría de casos:
Un solo bucle 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 cada otro elemento
for item_a in list_of_n_items:
for item_b in list_of_n_items:
compare(item_a, item_b)Búsqueda de tiempo constante: O(1)
Acceso por índice de matriz, búsqueda en tabla hash — un paso independientemente del tamaño.
Divide y vencerás (reduce el problema a la mitad en cada paso): O(log N)
Búsqueda binaria: cada verificación reduce a la mitad los elementos restantes.
---
O(N²) oculto: una lista dentro de un bucle
# Esto se ve como O(N) pero en realidad es O(N²)
visited = []
for item in list_of_n_items:
if item not in visited: # escanea todo 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. Un escaneo de 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 corrección toma un carácter: reemplaza visited = [] con visited = set(). Las pruebas de pertenencia en un conjunto cuestan O(1), no O(N). Un cambio. Los mismos resultados. 1.000× más rápido en N=1.000.
Clasifica y Arregla Este Código
Lee este código:
result = []
for name in student_names:
if name not in result:
result.append(name)La Teoría se Encuentra con la Práctica
Big O en la Vida Real
Big O no es solo teoría. Separa programas que terminan en segundos de programas que toman 17 minutos — en la exacta misma tarea.
Ejemplo real: detección de ciclos de dependencia en un sistema de construcción.
Cuando instalas software, tu computadora resuelve un gráfico de dependencias: el paquete A necesita B, B necesita C, y así sucesivamente. Un sistema de construcción verifica este gráfico en busca de ciclos.
Un algoritmo O(N²) de detección de ciclos funciona bien en N=100 paquetes. En N=50.000 paquetes (un proyecto real): toma 17 minutos. La corrección O(N): 10 segundos.
Este defecto exacto existe en GHC (compilador Haskell), pip (gestor de paquetes Python), Maven (sistema de construcción Java), Cargo (gestor de paquetes Rust) y 1.000+ otros proyectos.
No porque sus autores fueron descuidados. visited = [] fue escrito cuando N era pequeño. El código se calcificó. N creció. Nadie notó hasta que la construcción tomó media hora.
Big O es el vocabulario que te permite nombrar qué sucedió — & arreglarlo.
---
¿Quieres profundizar más? Nuestro curso unhamming incluye un capítulo completo sobre Big O, MOAD-0001 (un defecto O(N²) real encontrado en 1.000+ proyectos de código abierto), & por qué nombrar un patrón te permite encontrarlo en todas partes. Ver El Capítulo Faltante: Complejidad Algorítmica.
Predice Los Tiempos de Construcción
Un sistema de construcción utiliza detección de ciclos O(N²).
Tiempos de construcción medidos:
- N=100 paquetes: 0,01 segundos
- N=1.000 paquetes: 1 segundo
Para O(N²): el tiempo se escala como (N_nuevo / N_antiguo)².
Para O(N): el tiempo se escala como (N_nuevo / N_antiguo).