Algoritmos Avanzados en Python

Análisis de complejidad temporal

PyEnvíos recibe 2000 pedidos al día y quiere detectar los ids repetidos antes de cargar la camioneta. La primera versión compara cada pedido con todos los que vienen después: 1,999,000 comparaciones. La segunda recorre la lista una vez con un set: 2000 operaciones, y el mismo resultado, 50 ids repetidos. Ninguna cifra depende de la computadora. Esta lección da el lenguaje para predecir esa diferencia antes de escribir el código.

1. Contar operaciones, no segundos

El tiempo de reloj cambia con la máquina, el sistema operativo y lo que esté corriendo en paralelo. El número de operaciones básicas (comparaciones, accesos, llamadas) no cambia. Por eso el análisis de complejidad describe cómo crece ese número en función del tamaño de la entrada $n$. El doble ciclo hace una comparación por cada par de pedidos:

$$\binom{n}{2} = \frac{n(n-1)}{2} = \frac{2000 \cdot 1999}{2} = 1{,}999{,}000$$

Lo que importa no es la constante $\tfrac{1}{2}$, sino el término $n^2$: al duplicar los pedidos, las comparaciones se multiplican por cuatro.

2. Big O, Omega y Theta

La notación asintótica describe ese crecimiento ignorando constantes y términos menores:

• $O(f(n))$: cota superior. El algoritmo no crece más rápido que $f(n)$, salvo por una constante, para $n$ grande.
• $\Omega(f(n))$: cota inferior. No crece más lento que $f(n)$.
• $\Theta(f(n))$: ambas a la vez; el crecimiento es exactamente de ese orden.

Cuando alguien dice «la búsqueda binaria es $O(\log n)$», casi siempre se refiere al peor caso. Conviene separar tres casos. En la búsqueda lineal sobre 100,000 SKUs, el mejor caso es 1 comparación (el SKU está primero), el peor caso es 100,000 (está al final o no existe) y el caso promedio, medido con 1000 SKUs al azar, es 50,526: cerca de $n/2$. El peor caso y el promedio son $\Theta(n)$: la mitad de $n$ sigue siendo lineal.

3. La tabla de crecimiento

Con un millón de elementos, un algoritmo $O(n \log n)$ hace unos 20 millones de operaciones y uno $O(n^2)$, un billón. Ninguna mejora de hardware cierra una brecha de 50,000 veces. Más arriba en la escala están $O(2^n)$ y $O(n!)$, que aparecen en la mochila y en las rutas de reparto: ahí ni siquiera $n = 30$ es manejable por fuerza bruta.

4. El costo de las operaciones de Python

Muchos algoritmos cuadráticos se esconden en una sola línea. La wiki TimeComplexity de Python documenta los costos en CPython:

• x in lista: $O(n)$, recorre la lista. x in conjunto y clave in dic: $O(1)$ en promedio, porque usan tablas hash.
• lista.append(x): $O(1)$ amortizado. De vez en cuando la lista se redimensiona, pero ese costo repartido entre todas las inserciones es constante.
• lista.insert(0, x) y lista.pop(0): $O(n)$, desplazan todos los elementos. Para una cola, collections.deque lo hace en $O(1)$.
• sorted y lista.sort(): $O(n \log n)$.

El caso de los pedidos repetidos, en las dos versiones:

import random

r5 = random.Random(5)
pedidos = [r5.randint(1, 50_000) for _ in range(2000)]

comps, rep1 = 0, set()
for i in range(len(pedidos)):
    for j in range(i + 1, len(pedidos)):
        comps += 1
        if pedidos[i] == pedidos[j]:
            rep1.add(pedidos[i])

vistos, rep2 = set(), set()
for x in pedidos:
    if x in vistos:
        rep2.add(x)
    vistos.add(x)
print(comps, len(pedidos), len(rep1), rep1 == rep2)   # 1999000 2000 50 True

La segunda versión es $O(n)$ porque cada in sobre el set cuesta $O(1)$ en promedio. Si vistos fuera una lista, la línea x in vistos sería lineal y el algoritmo volvería a ser cuadrático sin que el código lo parezca.

5. Complejidad espacial

La memoria también se analiza. El doble ciclo usa $O(1)$ memoria extra; la versión con set usa $O(n)$: guarda hasta 2000 ids. En CPython 3.13, sys.getsizeof reporta 16,184 bytes para la lista de pedidos y 131,288 para el set con sus 1949 ids distintos: unas 8 veces más, porque la tabla hash deja huecos libres para mantener las búsquedas rápidas. Cambiar memoria por tiempo es el intercambio más común en optimización; la memoización de la siguiente lección es otro ejemplo.

Trampas comunes

• Medir con un solo timeit y concluir: el reloj mezcla el algoritmo con la máquina. Cuenta operaciones o compara proporciones al duplicar $n$.
• Olvidar el costo de las operaciones internas: un in sobre lista dentro de un ciclo convierte $O(n)$ en $O(n^2)$.
• Confundir promedio con garantía: el $O(1)$ de set y dict es promedio; con colisiones extremas se degrada.
• Despreciar constantes con $n$ pequeño: con 10 elementos, una lista puede ganarle a un set; Big O habla de crecimiento.
• Ignorar la memoria: una solución $O(n)$ en tiempo que no cabe en RAM no sirve.

Cierre

En el notebook complejidad-y-recursion se duplica $n$ varias veces y se observa cómo crece cada conteo. Antes de optimizar una función, escribe su complejidad en un comentario y busca la línea que domina; casi siempre es un ciclo con una operación lineal adentro.