Complejidad espacial: cómo analizar la memoria de tus algoritmos

Al hablar de eficiencia, todos piensan en tiempo. Pero la complejidad espacial — cuánta memoria usa un algoritmo — es igual de crítica, especialmente en sistemas con recursos limitados.

¿Qué es la complejidad espacial?

Mide la memoria adicional que necesita un algoritmo, expresada en notación Big O.

Ejemplos prácticos

O(1) — Espacio constante

def suma(arr):
    total = 0  # Solo una variable, sin importar n
    for num in arr:
        total += num
    return total

O(n) — Espacio lineal

def duplicar(arr):
    return [x * 2 for x in arr]  # Nueva lista del mismo tamaño

O(n²) — Espacio cuadrático

def matriz_identidad(n):
    return [[1 if i==j else 0 for j in range(n)] for i in range(n)]
# Para n=1000: un millón de celdas

La recursión consume stack

Cada llamada recursiva ocupa memoria en el call stack:

def factorial(n):
    if n <= 1: return 1
    return n * factorial(n - 1)
# factorial(10000) → RecursionError

Versión iterativa equivalente con O(1) espacio:

def factorial_iter(n):
    resultado = 1
    for i in range(2, n + 1):
        resultado *= i
    return resultado

Trade-off tiempo vs espacio

# Fibonacci O(n) tiempo, O(n) espacio
def fib_tabla(n):
    tabla = [0, 1] + [0] * (n - 1)
    for i in range(2, n+1):
        tabla[i] = tabla[i-1] + tabla[i-2]
    return tabla[n]

# O(n) tiempo, O(1) espacio — mejor
def fib_optimo(n):
    prev, curr = 0, 1
    for _ in range(2, n+1):
        prev, curr = curr, prev + curr
    return curr

Generadores: O(1) para colecciones grandes

# MAL: lista completa en memoria
cuadrados = [x**2 for x in range(1_000_000)]  # ~8MB

# BIEN: un elemento a la vez
def cuadrados_gen(n):
    for x in range(n):
        yield x**2  # O(1) memoria

Cuando analices tu código, evalúa siempre las dos dimensiones: tiempo y espacio. En sistemas con millones de elementos, la diferencia entre O(n) y O(1) de espacio puede ser la diferencia entre que funcione o no.