java - programacion - how to calculate space complexity

¿Es correcto mi análisis de la complejidad del espacio?

Question

Este es el problema 9.5 de Cracking the Coding Interview ^5ª edición

El problema: escribe un método para calcular todas las permutaciones de una cadena

Aquí está mi solución, codificada en Java (pruébala, funciona :))

public static void generatePerm(String s) {
Queue<Character> poss = new LinkedList<Character>();
int len = s.length();
for(int count=0;count<len;count++)
poss.add(s.charAt(count));
generateRecurse(poss, len, "");
}
private static void generateRecurse(Queue<Character> possibles, int n, String word) {
if(n==0)
System.out.println(word);
else {
for(int count=0;count<n;count++) {
char first = possibles.remove();
generateRecurse(possibles, n-1, word+first);
possibles.add(first);
}
}
}

Estuve de acuerdo con el autor en que mi solución funciona en O (n!) Complejidad de tiempo porque para resolver este problema, debe considerar los factores, como para una palabra como "arriba", hay tres posibilidades para la primera letra, 2 para el segundo y así sucesivamente ...

Sin embargo, ella no hizo ninguna mención de la complejidad del espacio. Sé que a los entrevistadores les encanta preguntarle la complejidad del tiempo y el espacio de su solución. ¿Cuál sería la complejidad espacial de esta solución?

Mi suposición inicial fue O (n ² ) porque hay n llamadas recursivas en cada nivel n. Entonces agregaría n + n - 1 + n - 2 + n - 3 ..... + 1 para obtener ^{n (n + 1)} / ₂ que está en O (n ² ). Razoné que no hay n llamadas recursivas, porque tiene que retroceder n veces en cada nivel y que la complejidad del espacio es la cantidad de llamadas recursivas que realiza su algoritmo. Por ejemplo, al considerar todas las permutaciones de "TOP", a nivel, 3 llamadas recursivas, gR ([O, P], 2, "T"), gR ([P, T], 2, "O"), gR ([T, O], 2, "P") están hechos. ¿Es correcto mi análisis de la complejidad del espacio?

Answer 1

Creo que tienes la respuesta correcta, pero por el motivo equivocado. La cantidad de llamadas recursivas no tiene nada que ver con eso. Cuando haces una llamada recursiva, agregará una cierta cantidad de espacio a la pila; pero cuando esa llamada sale, se libera el espacio de la pila. Entonces supongamos que tienes algo como esto:

void method(int n) {
if (n == 1) {
for (int i = 0; i < 10000; i++) {
method(0);
}
}
}
method(1);

Aunque el method llama a sí mismo 10000 veces, todavía no habrá más de 2 invocaciones de method en la pila en un momento dado. Entonces, la complejidad del espacio sería O (1) [constante].

La razón por la cual su algoritmo tiene una complejidad de espacio O (n ² ) se debe a la word cadena. Cuando n baja a 0, las invocaciones de generateRecurse ocuparán las entradas de la pila de len . Habrá entradas de la pila len como máximo, por lo que el uso del espacio de la pila solo será O (n); pero cada una de esas entradas de pila tiene su propia word , que todas existirán en el montón al mismo tiempo; y las longitudes de esos parámetros de word son 1, 2, ..., len , que por supuesto suman (len * (len+1)) / 2 , lo que significa que el uso del espacio será O (n ² ).

MÁS SOBRE LOS MARCOS DE APILAMIENTO: Parece que una explicación de los fundamentos de los marcos de pila sería útil ...

Un "marco de pila" es solo un área de memoria que es parte de la "pila". Típicamente, la pila es un área de memoria predefinida; la ubicación y el tamaño de los marcos de pila, sin embargo, no están predefinidos. Cuando se ejecuta por primera vez un programa, no habrá nada en la pila (de hecho, probablemente habrá algunos datos iniciales allí, pero digamos que no hay nada, solo para mantener las cosas simples). Entonces, el área de pila de la memoria se ve así:

bottom of stack top of stack
------------------------------------------------------------------
| nothing |
------------------------------------------------------------------
^
+--- stack pointer

(Esto supone que la pila crece hacia arriba, de direcciones inferiores a superiores. Muchas máquinas tienen pilas que crecen hacia abajo. Para simplificar, seguiré suponiendo que se trata de una máquina cuya pila crece hacia arriba).

Cuando se llama a un método (función, procedimiento, subrutina, etc.), se asigna un área determinada de la pila. El área es suficiente para contener las variables locales del método (o referencias a ellas), los parámetros (o referencias a ellos), algunos datos para que el programa sepa dónde volver cuando return , y posiblemente otra información - la otra información es altamente dependiente de la máquina, el lenguaje de programación y el compilador. En Java, el primer método será main

bottom of stack top of stack
------------------------------------------------------------------
| main''s frame | nothing |
------------------------------------------------------------------
^
+--- stack pointer

Tenga en cuenta que el puntero de la pila se ha movido hacia arriba. Ahora llamadas main method1 . Como el method1 volverá a main , las variables locales y los parámetros de main deben conservarse para cuando main pueda reanudar la ejecución. Se asigna un nuevo marco, de algún tamaño, en la pila:

bottom of stack top of stack
------------------------------------------------------------------
| main''s frame | method1''s frame | nothing |
------------------------------------------------------------------
^
+--- stack pointer

y luego method1 llama a method2 :

bottom of stack top of stack
------------------------------------------------------------------
| main''s frame | method1''s frame | method2''s frame | nothing |
------------------------------------------------------------------
^
+--- stack pointer

Ahora el method2 regresa. Después de que el method2 regrese, sus parámetros y variables locales ya no serán accesibles. Por lo tanto, se puede descartar todo el cuadro. Esto se hace moviendo el puntero de pila nuevamente a donde estaba antes. (El "puntero de pila anterior" es una de las cosas guardadas en algunos cuadros.) La pila vuelve a verse así:

bottom of stack top of stack
------------------------------------------------------------------
| main''s frame | method1''s frame | nothing |
------------------------------------------------------------------
^
+--- stack pointer

Esto significa que, en este punto, la máquina verá la parte de la pila que comienza con el puntero de la pila como "no utilizada". No es realmente correcto hablar del marco del method2 siendo reutilizado. Realmente no puedes usar algo que ha dejado de existir, y el marco de method2 ya no existe. Conceptualmente, todo lo que hay es una gran área vacía de la pila. Si method1 llama a otro método, ya sea method2 , method1 recursively, System.out.println u otra cosa, se creará un nuevo frame en el lugar al que apunte el puntero de la pila. Este marco podría ser más pequeño, igual o más grande que el cuadro del method2 . Tomará parte o la totalidad de la memoria donde estaba el marco del method2 . Si se trata de otra llamada a method2 , no importa si se llama con los mismos o diferentes parámetros. No puede importar, porque el programa no recuerda qué parámetros se usaron la última vez. Todo lo que sabe es que el área de memoria que comienza con el puntero de la pila está vacía y disponible para su uso. El programa no tiene idea de qué cuadro vivió más recientemente allí. Ese marco se ha ido, ido, ido.

Si puedes seguir esto, puedes ver que al calcular la complejidad del espacio y al mirar solo la cantidad de espacio utilizado por la pila, lo único que importa es cuántos marcos pueden existir en la pila en cualquier punto en el tiempo. ? Los marcos que pueden haber existido en el pasado pero que ya no existen no son relevantes para el cálculo, sin importar con qué parámetros se invocaron los métodos.

(PD En caso de que alguien estuviera planeando señalar cómo estoy técnicamente equivocado sobre este o aquel detalle, ya sé que esto es una simplificación excesiva).