4 - Complejidad espacial

La complejidad espacial mide cuánta memoria adicional requiere un algoritmo además de la entrada. En C es clave porque gestionamos manualmente el stack y el heap.

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: un buffer del mismo tamaño que los datos → O(n).
  • Memoria superlineal: tablas o matrices derivadas de la entrada → O(n^2).

4.2 Variables, arrays, punteros, structs

En C cada tipo ocupa un tamaño fijo (por ejemplo, int suele ser 4 bytes en arquitecturas de 32/64 bits). Un array de n enteros consume O(n). Un struct combina campos y su tamaño es constante si no depende de n. Los punteros ocupan el tamaño de la dirección (4 u 8 bytes).

typedef struct {
  int id;
  double valor;
} Nodo; // ocupa espacio fijo, O(1) por instancia

Nodo lista[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).

int suma_recursiva(const int *v, int n) {
  if (n == 0) return 0;
  return v[0] + suma_recursiva(v + 1, n - 1); // profundidad n, espacio O(n)
}

Prefiere versiones iterativas cuando la profundidad puede ser grande o usa recursión con cola optimizable por el compilador si aplica.

4.4 Estructuras dinámicas (malloc/free)

Reservar memoria en el heap con malloc permite crear estructuras cuyo tamaño depende de la entrada. Hay que liberar con free para evitar fugas.

int *crear_buffer(int n) {
  int *buf = malloc(sizeof(int) * n); // O(n) espacio
  if (!buf) return NULL;
  return buf;
}

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

4.5 Casos típicos

  • O(1): conteos y índices en variables locales, un puntero temporal.
  • O(n): un array 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