驴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]));