Résoudre les récurrences en utilisant la méthode de substitution

Question

Donc, je suis en train de suivre un cours sur les algorithmes et j'ai un problème pour résoudre les récurrences et obtenir le temps de fonctionnement. Je me demandais si quelqu'un pourrait m'expliquer en termes simples comment résoudre en utilisant la méthode de substitution. L'algorithme B résout les problèmes de taille n en résolvant récursivement deux sous-problèmes de taille n - 1 puis en combinant les solutions en temps constant.

Ce qui m'a amené à venir avec la récurrence suivante: T(n)=2T(n-1)+O(1). Je suis ensuite venu avec O(1)=1. Ce qui m'a donné les éléments suivants: T(n)=2T(n-1)+1

Voici ma tentative de résoudre

T(n)=2T(n-1)+1 
=2(2T(n-2)+1)+1=4T(n-2)+3 
=4(2T(n-3)+1)+3=8T(n-3)+7 
=8(2T(n-4)+1)+7=16T(n-4)+15 
=16(2T(n-5)+1)+15=32T(n-5)+31 
=32T(2T(n-6)+1)+31=64T(n-6)+63 

Si je le fais bien, comment puis-je continuer à obtenir le temps d'exécution? Quelqu'un peut-il expliquer en termes simples comment utiliser la méthode de substitution?

Answer 1

Vous êtes proche, mais vous pouvez formater votre substitution arrière donc il est un peu plus de sens:

T(n) 
=2^1T(n-1)+(2^1-1) 
=2^2T(n-2)+(2^2-1) 
=2^3T(n-3)+(2^3-1) 
=2^4T(n-4)+(2^4-1) 
=2^5T(n-5)+(2^5-1) 
=2^6T(n-6)+(2^6-1) 
... 

Vous pouvez voir un modèle ici n approche 0. Il devient quelque chose comme 2^n + 2^n - 1, et en notation Big-O, O(2^n).

Une idée que j'avais qui pourrait vous aider avec d'autres relations de récurrence: la récurrence se produit n fois et chaque itération multiplie par 2. Semble quelque chose comme 2^n!