4 - Complejidad espacial

La complejidad espacial mide cuánta memoria adicional requiere un algoritmo además de la entrada. En Python es clave porque las estructuras incluyen sobrecarga y el manejo de memoria es automático.

4.1 ¿Qué es el uso de memoria?

Cuenta los bytes necesarios para variables, estructuras y buffers auxiliares. La notación Big-O resume cómo crece ese uso con n:

  • Memoria fija: un número constante de variables -> O(1).
  • Memoria proporcional: una lista auxiliar del mismo tamaño que los datos -> O(n).
  • Memoria superlineal: tablas o matrices derivadas de la entrada -> O(n^2).

4.2 Variables, listas, diccionarios, objetos

En Python los objetos tienen sobrecarga. Una lista de n referencias consume O(n), y un diccionario crece con la cantidad de pares clave/valor. Los atributos dentro de un objeto suman memoria adicional, aunque la gestión sea automática.

class Nodo:
  def __init__(self, nodo_id, valor):
    self.nodo_id = nodo_id
    self.valor = valor

lista = [Nodo(i, i * 0.5) for i in range(1000)]  # O(n) con n = 1000 elementos

4.3 Recursión y uso del stack

Cada llamada recursiva empuja un frame en el stack con sus variables y direcciones de retorno. Si la profundidad es n, el espacio es O(n) aunque el trabajo sea O(log n).

def suma_recursiva(valores, n):
  if n == 0:
    return 0
  return valores[0] + suma_recursiva(valores[1:], n - 1)  # profundidad n, espacio O(n)

Prefiere versiones iterativas cuando la profundidad puede ser grande o controla el límite de recursión si aplica.

4.4 Estructuras dinámicas

En Python las estructuras crecen dinámicamente. Una lista o un diccionario expanden su capacidad cuando es necesario, lo que implica sobre-asignación para amortiguar el costo de crecimiento.

def crear_buffer(n):
  return [0] * n  # O(n) espacio

Listas enlazadas, árboles y grafos almacenan referencias extra; su costo espacial incluye nodos y enlaces.

4.5 Casos típicos

  • O(1): conteos e índices en variables locales, una referencia temporal.
  • O(n): una lista auxiliar del mismo tamaño que la entrada, o la pila de recursión con profundidad n.
  • O(n^2): una matriz de adyacencia para un grafo de n nodos o tablas de programación dinámica con dimensiones n × n.

4.6 Trade-offs espacio/tiempo

Elegir estructuras afecta tiempo y memoria:

  • Usar un buffer extra puede reducir operaciones (más memoria, menos tiempo), como en MergeSort.
  • Evitar memoria extra puede aumentar el tiempo, como ordenar in-place con QuickSort.
  • Cachear resultados (memoización) acelera cálculos repetidos a costa de crecer a O(n) o más en espacio.
  • Las estructuras compactas (bitsets) reducen espacio, pero agregan trabajo en operaciones bit a bit.
Retornar