Notación Big O Explicada con Ejemplos de Código

Una búsqueda en un diccionario de Python tarda unos 100 nanosegundos, tanto si el diccionario tiene 1.000 claves como 1.000.000. Un bucle anidado que busca duplicados en una lista tarda medio milisegundo con 200 elementos y 136 milisegundos con 3.200. Dieciséis veces la entrada, casi 280 veces la espera. Misma máquina, mismo Python. La notación Big O es el nombre de esa diferencia.

Qué mide la notación Big O

Big O describe cómo crece el tiempo de ejecución (o el uso de memoria) de un fragmento de código a medida que la entrada se hace más grande. No es una lectura de cronómetro y no le importa si tu portátil es rápido o lento. Le importa la forma de la curva de crecimiento: al duplicar la entrada, ¿el tiempo se duplica, se cuadruplica o apenas se mueve?

La notación elimina todo lo que no cambia esa forma, desde los factores constantes hasta el hardware en el que corre el código. O(n) significa “proporcional a n”, ya sea que el coste real sea 3n + 7 o 0.001n + 1000000. Haz que n sea lo bastante grande y solo queda la forma.

Ejemplos de Big O en Python, cronometrados con entradas crecientes

Cada función de abajo se cronometró con el módulo timeit de Python en Python 3.11, con tamaños de entrada separados por un orden de magnitud (o el doble).

Tiempo constante: una búsqueda en diccionario

1
2

def dict_lookup(d, key):
    return d[key]

La entrada crece mil veces. El tiempo por llamada se mantiene plano, dentro del ruido de medición. Un diccionario es una tabla hash: Python calcula el hash de la clave y salta directo al bucket correspondiente, sin importar cuántas otras entradas existan. Esto es O(1), tiempo constante.

Tiempo lineal: sumar una lista

1
2
3
4
5

def sum_loop(nums):
    total = 0
    for n in nums:
        total += n
    return total

Cada aumento de diez veces en n trae un aumento de tiempo de aproximadamente diez veces. El bucle toca cada elemento exactamente una vez, así que el trabajo escala directamente con la entrada. Esto es O(n), tiempo lineal, y es donde vive la mayoría del código del día a día.

Tiempo cuadrático: buscar duplicados de la forma ingenua

1
2
3
4
5
6

def has_duplicate_naive(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

Duplicar n cuadruplica aproximadamente el tiempo en cada paso. El bucle externo corre n veces y el interno corre casi n veces por cada iteración externa, así que el trabajo total es proporcional a n * n. Esto es O(n^2), tiempo cuadrático. Es la clase que arruina el código en producción, porque se ve bien en una prueba con 50 filas y agota el tiempo de espera con 50.000.

Tiempo logarítmico: búsqueda binaria

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def binary_search(sorted_nums, target):
    lo, hi = 0, len(sorted_nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sorted_nums[mid] == target:
            return mid
        elif sorted_nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Un aumento de mil veces en n apenas duplica el tiempo. Cada paso del bucle descarta la mitad del rango restante, así que el número de pasos necesarios crece con log2(n) en lugar de con n: unos 10 pasos para mil elementos, unos 20 para un millón. Esto es O(log n). Git bisect ejecuta el mismo algoritmo sobre el historial de commits en vez de un array ordenado: encuentra el commit que rompió algo entre cientos de candidatos en un puñado de pasos, porque cada prueba descarta la mitad del rango restante.

Tiempo linearítmico: ordenar

1

sorted_nums = sorted(nums)

Cada paso de diez veces en n cuesta más de diez veces en tiempo, pero muy por debajo del cien veces que mostraría un algoritmo cuadrático. El sorted() de Python usa Timsort, que hace O(n log n) comparaciones: el merge procede en más o menos log n rondas, y cada ronda toca cada uno de los n elementos una vez para fusionar las secuencias adyacentes. Todo ordenamiento de propósito general que usarás en el día a día (Timsort, mergesort, el caso promedio de quicksort) termina aquí, por eso O(n log n) se trata como “lo mejor que puede dar un ordenamiento” en lugar de compararlo con O(n).

Las clases de complejidad Big O más comunes, de la más rápida a la más lenta

Mira las dos últimas filas. Pasar de O(n log n) a O(n^2) con un millón de elementos es la diferencia entre un informe que corre en un segundo y uno que sigue corriendo cuando alguien mata el proceso.

Lo que la notación Big O no dice

Big O describe el crecimiento asintótico, es decir, lo que pasa cuando n se vuelve arbitrariamente grande. Tres cosas se escapan por ese hueco.

Las constantes son invisibles. Un O(n) con un factor constante de 1000 puede ser más lento en la práctica que un O(n^2) con una constante minúscula, para cualquier n que vayas a ver alguna vez. Big O te dice qué curva gana al final, no qué función es más rápida con tus datos. Por eso el insertion sort, que es O(n^2), sigue siendo la mejor opción para arrays muy pequeños, y por eso Timsort usa un insertion sort binario para construir cada pequeña secuencia (run) hasta una longitud mínima (minrun, típicamente 32-64 elementos) antes de empezar a fusionarlas.

Un n pequeño no muestra la curva. Los tiempos cuadráticos de arriba solo se hicieron evidentemente cuadráticos cuando n superó unos cientos. Con n = 10 casi cualquier cosa termina antes de que lo notes, por eso una función puede pasar todas las pruebas que escribas en local y luego fallar con los volúmenes de datos de producción.

La complejidad espacial es un eje aparte. dict_lookup, sum_loop, has_duplicate_naive y binary_search corren todas con memoria extra prácticamente constante: ninguna reserva una segunda estructura de datos proporcional a la entrada. sorted() no: devuelve una lista nueva del mismo tamaño que la entrada, O(n) de espacio, porque nunca ordena in situ. Algunos algoritmos intercambian memoria por velocidad a propósito: una función de Fibonacci con memoización guarda cada resultado ya calculado, gastando O(n) de espacio para convertir O(2^n) de tiempo en O(n). Cuando indiques la complejidad de una función, di a qué eje te refieres: la versión más rápida suele ser la que usa más memoria.

Cómo detectar un O(n^2) escondido en tu código

El bucle anidado de antes es el caso obvio. El que llega a producción normalmente no tiene ningún bucle anidado a la vista.

Comprobaciones de pertenencia dentro de un bucle. x in alguna_lista es O(n) en una lista, porque Python tiene que recorrerla entera. Ejecutar esa comprobación dentro de un bucle que ya corre n veces te da O(n^2) sin un segundo for a la vista:

1
2
3
4
5
6

# O(n^2): "in" recorre toda la lista en cada iteración
seen = []
for item in items:
    if item in seen:
        continue
    seen.append(item)

Cambia la lista por un set, donde la pertenencia es O(1), y el bucle baja a O(n):

1
2
3
4
5
6

# O(n): "in" es una búsqueda hash
seen = set()
for item in items:
    if item in seen:
        continue
    seen.add(item)

Reconstruir una lista en vez de añadirle elementos. result + [item] reserva una lista nueva y copia dentro cada elemento ya existente; result.append(item) hace crecer la lista existente in situ.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def build_with_plus(n):
    result = []
    for i in range(n):
        result = result + [i]   # copia todo lo construido hasta ahora, cada vez
    return result

def build_with_append(n):
    result = []
    for i in range(n):
        result.append(i)        # O(1) amortizado
    return result

Construir una lista de 8.000 elementos con + tardó 65 ms. La misma lista con .append() tardó 0,15 ms. La diferencia se agranda a medida que n crece, porque uno es cuadrático y el otro es lineal.

La consulta N+1. Recuperas una lista de filas y luego las recorres lanzando una consulta más por fila para los datos relacionados, y una sola consulta se ha vuelto n + 1: O(n) idas y vueltas a la base de datos en vez de una. Un índice, como se explica en cómo funcionan los índices de base de datos, convierte una búsqueda única de un escaneo O(n) de la tabla a O(log n). No hace nada por un bucle que manda mil consultas separadas. La solución tiene la misma forma que la del set de antes: reemplaza la operación por fila con una operación hecha una sola vez. Aquí significa una sola consulta con un join, que los tipos de JOIN en SQL explicados con ejemplos recorre en detalle.

Cómo medir la complejidad de tu propio código

Elige la función que sospechas, normalmente una con un bucle cuyo número de iteraciones depende del tamaño de los datos. Cronométrala con timeit en tres o cuatro tamaños de entrada, cada uno diez veces el anterior, y divide cada tiempo entre el anterior. Un ratio cercano a 1 es O(1) o O(log n). Cercano a 10 es lineal. Entre 10 y 100 es O(n log n), como el 17-21 que muestra la tabla de sorted(). Cercano a 100 significa que tienes un O(n^2) que cazar; si eso hace que los tamaños grandes sean demasiado lentos para esperar, duplica n en lugar de multiplicarlo por diez y busca un ratio cercano a 4. Empieza por las comprobaciones de pertenencia en listas y las reconstrucciones con + dentro de ese bucle, luego cualquier consulta enviada una vez por fila.

Artículos relacionados

• Git Bisect: Cómo Encontrar el Commit que Rompió tu Código
• Índices de Base de Datos: Cómo Funcionan y Cuándo Usarlos
• Tipos de JOIN en SQL Explicados con Ejemplos