La complejidad espacial mide cuánta memoria utiliza un algoritmo a medida que aumenta el tamaño de la entrada (n).
Mide cuántos recursos de memoria consume un algoritmo.

📌 Ejemplo:

• Un algoritmo que usa solo unas pocas variables tiene baja complejidad espacial.
• Un algoritmo que usa grandes estructuras de datos tiene alta complejidad espacial.

✅ Objetivo:
Queremos optimizar el uso de memoria para evitar que un programa consuma demasiados recursos.

📌 ¿Cómo se mide la Complejidad Espacial?

La memoria utilizada por un programa se divide en:

1. Memoria fija (O(1)):

   • Variables, constantes, punteros.
   • Independiente del tamaño de la entrada.

2. Memoria dinámica (O(n), O(n²), etc.):

   • Estructuras de datos como arrays, listas, diccionarios.
   • Depende del tamaño de la entrada n.

📌 Reglas generales:

• Si un algoritmo usa pocas variables, su complejidad es O(1).
• Si un algoritmo almacena un array con n elementos, su complejidad es O(n).
• Si un algoritmo usa una matriz n x n, su complejidad es O(n²).

📌 Comparación de Complejidades

https://praveendavidmathew.medium.com/big-o-notation-understanding-different-time-complexities-72fe847a6343

📌 1. Complejidad Espacial O(1) (Memoria Constante)

El algoritmo usa siempre la misma cantidad de memoria, sin importar n.

📌 Ejemplo: Uso de variables simples

1public class ConstantSpace {
2    public static int sum(int n) {
3        int total = 0; // Solo usa 1 variable
4        for (int i = 1; i <= n; i++) {
5            total += i;
6        }
7        return total;
8    }
9}

✅ Conclusión:
Aunque el bucle es O(n) en tiempo, la memoria usada no depende de n, por lo que es O(1) en espacio.

📌 2. Complejidad Espacial O(n) (Memoria Lineal)

El algoritmo usa memoria proporcional a n.

📌 Ejemplo: Guardar un array de n elementos

1public class LinearSpace {
2    public static int[] createArray(int n) {
3        int[] arr = new int[n]; // Usa memoria proporcional a n
4        for (int i = 0; i < n; i++) {
5            arr[i] = i;
6        }
7        return arr;
8    }
9}

✅ Conclusión:
El algoritmo necesita guardar n elementos, por lo que la memoria crece linealmente con n (O(n) en espacio).

📌 3. Complejidad Espacial O(n²) (Memoria Cuadrática)

El algoritmo usa una matriz de n × n elementos, lo que hace que la memoria crezca muy rápido.

📌 Ejemplo: Crear una matriz n × n

1public class QuadraticSpace {
2    public static int[][] createMatrix(int n) {
3        int[][] matrix = new int[n][n];
4        for (int i = 0; i < n; i++) {
5            for (int j = 0; j < n; j++) {
6                matrix[i][j] = i + j;
7            }
8        }
9        return matrix;
10    }
11}

✅ Conclusión:
Cada vez que n se duplica, la memoria se multiplica por 4. O(n²) puede volverse muy costoso en términos de espacio.

📌 4. Complejidad Espacial O(2ⁿ) (Explosión Combinatoria)

El algoritmo usa memoria exponencial porque genera todas las combinaciones posibles.

📌 Ejemplo: Guardar todas las subsecuencias posibles de una lista

1// Java - O(2ⁿ) - Generar subconjuntos
2import java.util.ArrayList;
3import java.util.List;
4
5public class ExponentialSpace {
6    public static void subsets(List<Integer> nums, List<Integer> temp, int start) {
7        System.out.println(temp);
8        for (int i = start; i < nums.size(); i++) {
9            temp.add(nums.get(i));
10            subsets(nums, temp, i + 1);
11            temp.remove(temp.size() - 1);
12        }
13    }
14
15    public static void main(String[] args) {
16        List<Integer> nums = List.of(1, 2, 3);
17        subsets(nums, new ArrayList<>(), 0);
18    }
19}

✅ Ejemplo real:
Si tienes n objetos y quieres generar todas las combinaciones posibles, la memoria crece exponencialmente.