Complejidad de Espacio y Reglas

La complejidad de espacio mide cuánta memoria adicional usa un algoritmo más allá de los datos de entrada. Un algoritmo que crea una copia de los datos es O(n) en espacio. Un algoritmo que trabaja "in-place" sin crear estructuras adicionales es O(1) en espacio. La complejidad de espacio importa en sistemas con memoria limitada (dispositivos móviles, servidores con muchas peticiones simultáneas) o cuando los datos son muy grandes.

El trade-off tiempo-espacio es fundamental en algoritmos: muchos problemas se pueden resolver más rápido si usas más memoria. El ejemplo clásico es la memorización: en lugar de recalcular el mismo resultado repetidas veces (costoso en tiempo), guardas el resultado en un diccionario (costoso en espacio) y lo reutilizas. Este patrón, llamado caché o memoization, transforma muchos algoritmos exponenciales en lineales a costa de memoria adicional.

// Complejidad de espacio

// O(1) espacio - siempre usa la misma memoria
function sumaArray(arr) {
  let suma = 0; // Solo una variable extra
  for (const n of arr) suma += n;
  return suma;
}

// O(n) espacio - crece con el input
function duplicar(arr) {
  const result = []; // Array nuevo del mismo tamaño
  for (const n of arr) result.push(n * 2);
  return result;
}

// Trade-off: tiempo vs espacio (memoización)
// SIN memo: O(2^n) tiempo, O(n) espacio
function fibLento(n) {
  if (n <= 1) return n;
  return fibLento(n-1) + fibLento(n-2); // Recalcula todo
}

// CON memo: O(n) tiempo, O(n) espacio
function fibRapido(n, memo = {}) {
  if (n in memo) return memo[n]; // Cache!
  if (n <= 1) return n;
  memo[n] = fibRapido(n-1, memo) + fibRapido(n-2, memo);
  return memo[n];
}

// fib(40): lento = ~1seg | rápido = instantáneo

// Reglas del Big O:
// 1. Elimina constantes: O(2n) = O(n)
// 2. Toma el término mayor: O(n² + n) = O(n²)
// 3. Bucles separados: O(n) + O(m) = O(n + m)
// 4. Bucles anidados: O(n) * O(n) = O(n²)