Complexité temporelle: ces deux codes ont-ils la même complexité temporelle ou non? - récursivité, complexité temporelle

Je suis en train de lire un livre intitulé craquer l'interview de codage 6ème édition. En ce qui concerne complexité temporelle, voici un exemple de code pour les exécutions récursives (page 44):

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

Je pense que si le code suivant qui produit le même résultat numérique aurait la même complexité temporelle? Je suppose que ce ne serait pas?

   int f(int n) {
if (n <= 1){
return 1;
}
return 2 * f(n - 1);
}

additionnel: ce qui suit est le contexte du (premier) code dans le livre:

Réponses:

L'exécution deux fois, une fonction n'est pas la même chose que multiplier la valeur de la fonction à ce moment-là par 2. Imaginez une exécution de fonction comme deux instructions en cours d'exécution.

Alors quand tu fais:

 return f(n-1) + f(n-1) //In your definition of f(n)

Pour calculer f(n), f(n-1) doit être calculé deux fois. Et ensuite pour calculer f(n-1), f(n-2) doit être calculé deux fois à son tour. Ainsi, les appels d'exécution se développent sous la forme d'un arbre, en se multipliant deux fois à chaque niveau. Cela ressemble à quelque chose comme ceci au format pictural:

Cependant, dans votre deuxième définition où:

return 2 * f(n-1) //In your definition of f(n)

Pour calculer f(n), nous calculons f(n-1) une fois que seulement, puis nous le multiplions par 2, ce qui n’affecte pas la complexité globale du programme en termes de nombre n. Notez que nous ne sauvegardons pas les valeurs intermédiaires de f(n-1) ou f(n-2) n'importe où et c’est pourquoi je dis qu’ils sont calculés à chaque fois, sinon le scénario aurait été différent.Alors dans votre cas, le programme progresse quelque chose comme:

Essayez de relire vos définitions de fonctions et de les visualiser en termes d’instructions à exécuter à chaque itération. Vous arriverez à deux images similaires dans votre esprit.

J'espère que cela vous permettra de commencer dans la bonne direction.