Algoritmos que terminan a tiempo: Una verificación rápida de complejidad

Escribes una función, la ejecutas en tus datos de prueba y funciona bien. Luego llega a producción — 500,000 filas en lugar de 500 — y la solicitud expira. Esto sucede constantemente, y casi siempre es un problema de complejidad oculto detrás de código que parecía razonable a pequeña escala.

Por qué tu laptop te engañó

Un algoritmo O(n²) ejecutándose en 100 elementos realiza 10,000 operaciones. Eso es instantáneo en cualquier máquina. Ejecuta el mismo algoritmo en 100,000 elementos y llegas a 10 mil millones de operaciones — minutos u horas en lugar de milisegundos. El salto de n a n² no parece peligroso hasta que n se hace grande, que es exactamente por qué se cuela en las revisiones de código y en las pruebas locales.

Un ejemplo clásico: verificar duplicados con un bucle anidado.

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

Esto es O(n²). Cámbialo por un set:

def has_duplicates(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

Ahora es O(n). Las búsquedas en set son O(1) en promedio, así que toda la función escala linealmente en lugar de cuadráticamente. En 10,000 elementos esa es la diferencia entre aproximadamente 100 millones de comparaciones y 10,000.

Mide antes de optimizar

No adivines. Usa timeit para microbenchmarks:

import timeit
timeit.timeit(lambda: has_duplicates(list(range(5000))), number=10)

Para funciones más grandes, perfila con cProfile:

python -m cProfile -s cumulative myscript.py

Mira la columna cumtime. Si una función consume el 90% del tiempo de ejecución, ese es tu objetivo. Optimizar código que no es el cuello de botella desperdicia tu tiempo y añade complejidad sin ganancia.

Patrones comunes que se vuelven lentos silenciosamente

Comprobaciones repetidas de pertenencia a una lista. if x in my_list es O(n) para una lista pero O(1) en promedio para un set o dict. Si estás verificando pertenencia dentro de un bucle, esa comprobación O(n) dentro de un bucle O(n) te da O(n²) en total. Cambia la lista por un set y vuelves a O(n).

Concatenación de strings en un bucle. En Python, result += chunk dentro de un bucle sobre strings es O(n²) en el peor caso porque los strings son inmutables y cada concatenación copia el todo. Usa ''.join(chunks) en su lugar — construye el string una sola vez.

Ordenar cuando no lo necesitas. sorted() es O(n log n). Si lo estás llamando dentro de un bucle solo para encontrar el máximo o mínimo en cada iteración, usa max()/min() (O(n)) o mejor aún, un heap (heapq) si necesitas el extremo corriente repetidamente. heapq.nlargest(k, data) es O(n log k), mucho más barato que ordenar toda la lista cuando k es pequeño.

Funciones recursivas sin memoización. Fibonacci recursivo ingenuo es O(2ⁿ) porque recomputa los mismos subproblemas una y otra vez. Añade functools.lru_cache y baja a O(n):

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Leyendo Big O del código real, rápidamente

Cuenta bucles anidados sobre la misma entrada — ese es usualmente tu exponente. Un bucle único es O(n). Un bucle dentro de un bucle es O(n²) a menos que el rango del bucle interno se reduzca (como en la forma optimizada de ordenamiento de burbuja, aún O(n²) en el peor caso pero menos comparaciones). Llamadas recursivas que dividen el problema por la mitad, como búsqueda binaria u ordenamiento por mezcla, apuntan a O(log n) u O(n log n). Llamadas recursivas que se ramifican en múltiples llamadas por nivel, como Fibonacci ingenuo, apuntan a tiempo exponencial — una señal fuerte de que necesitas memoización o una reescritura iterativa.

Un buen hábito: antes de escribir bucles anidados o recursión sobre datos que enfrenta el usuario, pregúntate qué tan grande podría ser n realísticamente en producción, no en tu archivo de prueba. Si n podría alcanzar seis cifras, una solución O(n²) necesita una segunda mirada antes de que llegue.

Para más sobre análisis de complejidad, algoritmos de ordenamiento y herramientas de perfilado, consulta los segmentos de Python y Ciencias de la Computación en Korra Studio.