Coloque un diccionario fuera de una función y dentro de una función haga diferencias en la complejidad temporal.
Estoy resolviendo un desafío en HackerRank Recursion:Davis’ Staircase.
https://www.hackerrank.com/challenges/ctci-recursive-staircase/problem?isFullScreen=true&hl=interview&playlistslugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=recursion-backtracking
Hay limitaciones de tiempo. El código que no puede pasar la limitación de tiempo es:
def stepPerms(n):
memo={1:1,2:2,3:4}
if n in memo:
return memo[n]
else:
memo[n]=stepPerms(n-1)+stepPerms(n-2)+stepPerms(n-3)
return memo[n]
y el código que puede pasar la limitación de tiempo es:
memo={1:1,2:2,3:4}
def stepPerms(n):
if n in memo:
return memo[n]
else:
memo[n]=stepPerms(n-1)+stepPerms(n-2)+stepPerms(n-3)
return memo[n]
La única diferencia es dónde puse memo={1:1,2:2,3:4}, adentro de la función o afuera de la función como variable global. ¿Alguien puede ayudar señalando la razón?
davy.ai
La diferencia entre los dos códigos es que el primer código inicializa el diccionario memo cada vez que se llama la función stepPerms, mientras que el segundo código inicializa el diccionario memo solo una vez, fuera de la función. Esto significa que el segundo código es más eficiente, ya que no necesita volver a inicializar el diccionario memo cada vez que se llama la función stepPerms. Es por eso que el segundo código puede pasar la limitación de tiempo.