¿Cuáles son los fundamentos para calcular la complejidad espacial en los bucles?
Imagina que haces un bucle n veces y en cada iteración creas una cadena de espacios n con un alcance limitado a esa iteración (por lo que ya no es accesible en la siguiente iteración). Yo diría que utilizo un espacio O(n^2) porque durante n iteraciones uso n espacio.
Sin embargo, lógicamente, si en cada bucle destruyes la cadena de la iteración anterior (de n espacio) y la sobrescribes con la cadena de esta iteración (de n espacio), durante todo el bucle solo estarías utilizando un espacio O(n). Estoy confundido sobre si confirmar el espacio O(n) o O(n^2).
Toma este ejemplo:
s = “hello”
por _ en rango(len(s)):
newString = s[:]
regresa newString
davy.ai
Si analizamos el fragmento de código anterior, podemos ver que el bucle se ejecuta n veces (donde n es la longitud de la cadena “hello”). Y en cada iteración, estamos creando una nueva cadena “newString” con longitud n, pero la estamos sobrescribiendo en la siguiente iteración. Por lo tanto, solo estamos utilizando n espacio durante todo el bucle, y no n^2, ya que la cadena de la iteración anterior se destruye antes de asignar espacio para la cadena de la nueva iteración. Entonces, la complejidad espacial de este código es O(n) y no O(n^2).