Complejidad espacial: ¿cuánta memoria se utiliza?

Al finalizar este tema

Comprenderá qué es la complejidad espacial, su relación con la complejidad temporal y cuándo debe prestar atención al uso de la memoria en la práctica.

Pensar que solo importa la velocidad

Al evaluar algoritmos, es fácil pensar únicamente en "qué tan rápido es". Se analiza la complejidad temporal comparando la notación Big-O como O(n), O(n log n) y O(n^2).

Sin embargo, una computadora no solo tiene CPU. También tiene memoria (RAM). Por muy rápido que sea un algoritmo, si utiliza 100 GB de memoria, normalmente no se podrá ejecutar en una computadora convencional.

La complejidad espacial consiste en analizar cuánta memoria utiliza un algoritmo en función del tamaño de la entrada. Se utiliza la misma notación Big-O que la complejidad temporal.

O(1) — Memoria fija independiente de la entrada

def find_max(arr):
    result = arr[0]
    for x in arr:
        if x > result:
            result = x
    return result

Tanto si el arreglo tiene 100 elementos como un millón, la única variable adicional que se utiliza es result. La complejidad espacial es O(1), lo que se conoce como "espacio constante".

O(n) — Memoria proporcional a la entrada

def get_squares(arr):
    result = []
    for x in arr:
        result.append(x * x)
    return result

Se crea un nuevo arreglo del mismo tamaño que el arreglo de entrada. Si la entrada tiene n elementos, se utiliza memoria adicional para n elementos. La complejidad espacial es O(n).

def reverse_string(s):
    return s[::-1]

Esto también es O(n), ya que se crea una nueva cadena con la misma longitud que la original.

O(n^2) — Estructura bidimensional

def create_matrix(n):
    return [[0] * n for _ in range(n)]

Al crear una matriz de n×n, la complejidad espacial es O(n^2). Un ejemplo representativo es la matriz de adyacencia.

El espacio oculto de la recursión

Cada vez que se llama a una función recursiva, se añaden marcos a la pila de llamadas. Esto también es memoria.

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

Al llamar a factorial(1000), se acumulan 1000 marcos en la pila de llamadas. La complejidad espacial es O(n). En Python, la profundidad de recursión predeterminada está limitada a 1000, por lo que si se supera este límite, se produce RecursionError.

Se puede reducir a O(1) mediante un bucle:

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

El resultado es el mismo, pero sin utilizar una pila. De esta manera, al convertir la recursión en un bucle, se puede ahorrar espacio.

Intercambio entre tiempo y espacio

"Si ahorras tiempo, usas más espacio; si ahorras espacio, tardas más". Esto se conoce como intercambio entre tiempo y espacio (Time-Space Tradeoff).

Un ejemplo representativo es el almacenamiento en caché (caching):

# Espacio O(1), tiempo O(n) — calcular cada vez
def fib(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# Espacio O(n), tiempo O(1) consulta — precalcular y almacenar
cache = {}
def fib_cached(n):
    if n in cache:
        return cache[n]
    if n <= 1:
        result = n
    else:
        result = fib_cached(n - 1) + fib_cached(n - 2)
    cache[n] = result
    return result

En lugar de usar más memoria, evitamos recalcular el mismo valor. Este intercambio (trade-off) es la esencia de la programación dinámica (DP).

Las tablas hash funcionan de manera similar. Al ordenar un arreglo para realizar una búsqueda binaria, el espacio adicional es O(1); sin embargo, al crear una tabla hash, se utiliza espacio adicional O(n) a cambio de que la búsqueda sea más rápida, con una complejidad de O(1).

Cuándo el espacio se convierte en un problema en la práctica

En el desarrollo web convencional, rara vez es necesario preocuparse por la complejidad espacial porque la RAM suele ser suficiente. No obstante, en las siguientes situaciones, la memoria se convierte en un cuello de botella:

Procesamiento de grandes volimentas de datos — Al analizar un archivo de registro de 10 GB, si se carga todo en la memoria, el sistema colapsará. Es necesario leer y procesar los datos línea por línea (streaming).

Dispositivos móviles/embebidos — Los smartphones o los dispositivos IoT tienen una RAM limitada. Los algoritmos deben diseñarse para utilizar poca memoria.

Pruebas de codificación — Los problemas suelen incluir condiciones como "límite de memoria: 256 MB". Una solución que utiliza un espacio de O(n^2) puede fallar por exceso de memoria.

Concepto clave

La complejidad espacial consiste en analizar cuánta memoria utiliza un algoritmo en función del tamaño de la entrada. La pila de llamadas (call stack) de la recursión también es espacio. Reemplazar la recursión con un bucle puede reducir el uso de memoria de O(n) a O(1). El tiempo y el espacio están en una relación de trade-off, y se debe decidir qué priorizar según la situación.