La notación Big O es el lenguaje que usamos los programadores para describir la eficiencia de un algoritmo. No mide el tiempo exacto que tarda (eso depende del hardware), sino cómo escala cuando la cantidad de datos crece.
¿Por qué importa?
Un algoritmo que tarda 1 segundo con 100 datos puede tardar 2 horas con 10.000 datos, o puede tardar 2 segundos. La diferencia está en su complejidad algorítmica, y Big O es cómo la expresamos.
Las complejidades más comunes
O(1) — Tiempo constante
El tiempo de ejecución no depende del tamaño de los datos.
def primer_elemento(lista):
return lista[0] # Siempre tarda lo mismo, sin importar el tamañoO(log n) — Logarítmico
El tiempo crece muy lentamente. Ejemplo: búsqueda binaria.
# Con 1.000 elementos: ~10 pasos
# Con 1.000.000 elementos: ~20 pasosO(n) — Lineal
El tiempo crece proporcionalmente al tamaño de los datos.
def suma_lista(lista):
total = 0
for num in lista: # Recorre todos los elementos
total += num
return totalO(n²) — Cuadrático
El tiempo crece con el cuadrado del tamaño. Peligroso para listas grandes.
def buscar_duplicados(lista):
for i in range(len(lista)):
for j in range(len(lista)): # Bucle dentro de bucle
if i != j and lista[i] == lista[j]:
return TrueTabla comparativa
| Notación | Nombre | n=10 | n=1000 | n=1.000.000 |
|---|---|---|---|---|
| O(1) | Constante | 1 | 1 | 1 |
| O(log n) | Logarítmico | 3 | 10 | 20 |
| O(n) | Lineal | 10 | 1.000 | 1.000.000 |
| O(n log n) | Linealítmico | 33 | 10.000 | 20.000.000 |
| O(n²) | Cuadrático | 100 | 1.000.000 | 10¹² |
Regla práctica
Cuando diseñes o elijas un algoritmo, apunta a O(n log n) o mejor. O(n²) empieza a ser problemático con más de 10.000 elementos. O(2ⁿ) es prácticamente inutilizable para n > 30.