¿Qué significa ‘Complejidad espacial’?

Complejidad espacial: 
el término Complejidad espacial se usa incorrectamente para el espacio auxiliar en muchos lugares. Las siguientes son las definiciones correctas de Espacio Auxiliar y Complejidad Espacial. 

El espacio auxiliar es el espacio adicional o espacio temporal utilizado por un algoritmo. 

La complejidad espacial de un algoritmo es el espacio total ocupado por el algoritmo con respecto al tamaño de entrada. La complejidad del espacio incluye tanto el espacio auxiliar como el espacio utilizado por la entrada. 

Por ejemplo, si queremos comparar algoritmos de clasificación estándar en función del espacio, el espacio auxiliar sería un mejor criterio que la complejidad del espacio. La ordenación por fusión utiliza el espacio auxiliar O(n), la ordenación por inserción y la ordenación por montón utilizan el espacio auxiliar O(1). Sin embargo, la complejidad espacial de todos estos algoritmos de clasificación es O(n). 

La complejidad del espacio es un concepto paralelo a la complejidad del tiempo. Si necesitamos crear una array de tamaño n, esto requerirá espacio O(n). Si creamos una array bidimensional de tamaño n*n, esto requerirá espacio O(n ² ).

En llamadas recursivas, el espacio de pila también cuenta. 

Ejemplo : 

int add (int n){
    if (n <= 0){
        return 0;
    }
    return n + add (n-1);
}

Here each call add a level to the stack :

1.  add(4)
2.    -> add(3)
3.      -> add(2)
4.        -> add(1)
5.          -> add(0)

Each of these calls is added to call stack and takes up actual memory.
So it takes O(n) space.

Sin embargo, el hecho de que tenga n llamadas en total no significa que ocupe O (n) espacio.

Mira la siguiente función:

int addSequence (int n){
    int sum = 0;
    for (int i = 0; i < n; i++){
        sum += pairSum(i, i+1);
    }
    return sum;
}

int pairSum(int x, int y){
    return x + y;
}

There will be roughly O(n) calls to pairSum. However, those 
calls do not exist simultaneously on the call stack,
so you only need O(1) space.

Nota: es necesario mencionar que la complejidad del espacio depende de una variedad de cosas, como el lenguaje de programación, el compilador o incluso la máquina que ejecuta el algoritmo.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.