Complejidad asintótica (Big-O)
Mapa conceptual
Big-O describe el término que domina cuando n crece, ignorando constantes y términos menores. Dos bucles anidados sobre n dan O(n²); un bucle simple y uno anidado siguen siendo O(n²). Un bucle más un anidado independientes (n + n²) es O(n²), porque n se desprecia frente a n².
La jerarquía de crecimiento
Crecimiento relativo (n en potencias de 2)
| n | 2n | 4n | 8n | 16n | |
|---|---|---|---|---|---|
| log n | 0 | 1 | 2 | 3 | 4 |
| n | 1 | 2 | 4 | 8 | 16 |
| n log n | 0 | 2 | 8 | 24 | 64 |
| n² | 1 | 4 | 16 | 64 | 256 |
La escala real importa: n = 10⁶ hace que O(n) sea factible (~un millón de pasos), O(n log n) cómodo, O(n²) inviable (10¹² pasos) y O(2ⁿ) inimaginable.
| Complejidad | Algoritmo típico | n = 1 000 |
|---|---|---|
| O(1) | acceso a índice, hash | 1 operación |
| O(log n) | búsqueda binaria | ≈ 10 operaciones |
| O(n) | recorrido lineal | 1 000 operaciones |
| O(n log n) | mergesort, quicksort medio | ≈ 10 000 |
| O(n²) | burbuja, dos bucles anidados | 1 000 000 |
| O(2ⁿ) | fuerza bruta de subconjuntos | absurdo |
No es solo tiempo: espacio
La complejidad espacial mide memoria extra. Un algoritmo in-place (ordena sin copiar la lista) es O(1) de espacio; uno que construye una copia es O(n). A veces se cambia espacio por tiempo: una tabla hash usa memoria extra para comprar búsquedas constantes.
¿Cuál es la complejidad temporal del siguiente código? for i in range(n): for j in range(n): x += 1
Un algoritmo O(n) es siempre más rápido en la práctica que uno O(n log n).
Ordena las clases de complejidad de más rápida (menos trabajo) a más lenta.
Más rápida
Intermedia
Más lenta
Une cada situación con la decisión de ingeniería que la complejidad sugiere.
Errores al estimar
- Contar operaciones internas y olvidar que n es el tamaño de la ENTRADA, no del resultado.
- Quedarse con el peor caso cuando el caso medio es representativo (quicksort: O(n²) pesimista pero O(n log n) medio).
- Ignorar la complejidad escondida de una operación: buscar en una lista es O(n), y meter eso dentro de un bucle convierte un O(n) en O(n²) sin que lo veas.
Ejemplo resuelto
- Analiza: for i in range(n): if i in lista_grande: ...
- El bucle exterior es O(n).
- Pero i in lista sobre una lista es O(m) con m el tamaño de la lista.
- Total: O(n·m), no O(n).
- Arreglo: convertir lista_grande a un conjunto (set) hace la pertenencia O(1) y el todo O(n).
En ciencia de datos, el 90 % de la lentitud de un pipeline no está en el modelo sino en estructuras mal elegidas: un in sobre una lista dentro de un bucle, un DataFrame filtrado fila a fila, o ordenar varias veces. Leer Big-O te dice dónde duele antes de escribir una línea.
Tabla de bolsillo
Análisis de algoritmos (repaso formal)
Notación asintótica, mejores y peores casos con ejemplos.
Tienes que responder «¿esta transacción es fraudulenta?» para 10⁷ transacciones. Un enfoque compara cada transacción con las 10⁴ anteriores (O(n·m)) y otro mantiene un conjunto de patrones vistos (O(n)). Calcula órdenes de magnitud de ambos y argumenta cuál usarías.
VisuAlgo
Visualizaciones animadas de estructuras de datos y algoritmos.