¿Qué significa Space Complexity?
Podemos utilizar Big O para analizar el space complexity (complejidad del espacio), que representa la cantidad de memoria adicional que necesitamos asignar para poder ejecutar el código de nuestro algoritmo.
En algunas ocasiones puedes haber escuchado acerca de auxiliar space complexity que se refiere al espacio requerido por el algoritmo, sin incluir el espacio requerido por los inputs (entradas).
Cuando hablamos de space complexity en realidad estamos hablando técnicamente de auxiliar space complexity. Es decir que nos enfocamos en lo que pasa dentro del algoritmo.
Space Complexity en JavaScript
Algunas reglas a considerar:
- La mayoría de los valores primitivos (booleans, numbers, undefined, null) tienen un espacio constante. El valor no es relevante.
- Los strings requieren un espacio O(n) en donde n es el número de caracteres.
- Los arrays y objects requieren un espacio O(n) en donde n es el la dimensión del arreglo o el número de keys para el objeto.
function sumar(arreglo) {
let total = 0;
for (let i = 0; i < arreglo.length; i++) {
total += arreglo[i];
}
return total;
}
En la anterior función el número de iteraciones depende de la longitud de arreglo, sin embargo, esto no es relevante para el space complexity, tampoco la dimensión de arreglo, que si bien ocupa espacio, lo que realmente nos resulta importante es el espacio adicional que requiere el algoritmo para ejecutarse. Al no requerir espacio adicional nuestra función es O(1).
Ahora analicemos la siguiente función. En este caso tomamos un arreglo y creamos uno nuevo, la dimensión de este depende de la dimensión del arreglo provisto, es decir es proporcional a n, la función tiene un O(n) para su space complexity.
function duplicar(arreglo) {
const nuevoArreglo = [];
for (let i = 0; i < arreglo.length; i++) {
nuevoArreglo.push(arreglo[i] * 2);
}
return nuevoArreglo;
}
console.log(duplicar([2, 3, 4]));
console.log(duplicar([1, 2, 3]));