Complejidad Espacial

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.

1. 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²).

2. 2. Comparación de Complejidades #

Fuente: miro.medium.com · Licencia: Licencia no indicada

Ampliar

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

3. 3. Complejidad Espacial O(1) (Memoria Constante) #

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

📌 Ejemplo: Uso de variables simples

✅ 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.

4. 4. Complejidad Espacial O(n) (Memoria Lineal) #

El algoritmo usa memoria proporcional a n.

📌 Ejemplo: Guardar un array de n elementos

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

5. 5. 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

✅ 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.

6. 6. 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.