Méthode de l'arbre Relation Relation

Question

Je suis actuellement en train de rencontrer des problèmes avec certains de nos problèmes de récurrence et comme j'ai des choses à venir bientôt, je pourrais vraiment utiliser de l'aide et peut-être une explication sur comment cela fonctionne.

J'ai donc essentiellement pseudocode pour résoudre la tour de Hanoi

TOWER_OF_HANOI (n, FirstRod, SecondRod, ThirdRod) 
    if n == 1 
      move disk from FirstRod to ThirdRod 
    else 
      TOWER_OF_HANOI(n-1, FirstRod, ThirdRod, SecondRod) 
       move disk from FirstRod to ThirdRod 
       TOWER_OF_HANOI(n-1, SecondRod, FirstRod, ThirdRod) 

Et à condition que je comprends comment écrire la relation (qui, honnêtement, je ne suis pas sûr que je fais ...) il devrait être T (n) = 2T (n-1) + Ɵ (n), n'est-ce pas? Je comprends en quelque sorte comment faire un arbre avec des sous-problèmes fractionnaires, mais même alors je ne comprends pas complètement le processus qui vous donnerait la solution finale de Ɵ (n) ou Ɵ (n log n) ou quoi que ce soit.

Merci pour toute aide, il serait grandement apprécié.

Answer 1

1. Supposons que la complexité de temps est T (n), il est censé être: T (n) = T (n-1) + T (n-1) + 1 = 2T (n-1) + 1. Pourquoi "+1" mais pas "+ n"? Comme "déplacer le disque de FirstRod vers ThirdRod" ne vous coûte qu'un seul coup.

2. Pour T (n) = 2T (n-1) + 1, son arbre de récursivité sera exactement comme ceci: https://www.quora.com/What-is-the-complexity-of-T-n-2T-n-1-+-C (. Vous trouverez peut-être utile, l'image est propre) C est une constante; cela signifie le coût par opération. Dans le cas de la Tour de Hanoi, C = 1.

3. Calculez la somme du coût de chaque niveau, vous trouverez facilement dans ce cas, le coût total sera 2^n-1, ce qui est exponentiel (coûteux). Par conséquent, la réponse de cette équation de récurrence est Ɵ (2^n).