Fermé . Cette question nécessite détails ou clarté . Il naccepte pas les réponses actuellement.
Commentaires
- Votre question comprend déjà une réponse complète au problème dorigine mais aucune question sur cette réponse. Ainsi, seules les réponses " yes / no " peuvent rester, ne vous aidant ni vous ni les futurs visiteurs. Veuillez lire les méta-discussions associées ici et ici et ajustez votre question en conséquence, par exemple en formulant une question spécifique sur un seul élément de votre réponse dont vous nêtes pas sûr. Si vous souhaitez uniquement des commentaires dordre général, nhésitez pas à nous rendre visite dans Chat informatique .
- @DavidRicherby Eh bien, essayez de ne pas regarder mon répondez et répondez-y, si vous le pouvez. Jai adoré ce site jusquà ce que tout le monde commence à trouver des défauts dans les questions posées plutôt que daider celui avec la question.
- Daprès ce que je pense que vous essayez de demander, oui $ T (n) $ serait en $ O (2 ^ n) $ mais vous ' d avez une borne supérieure plus serrée avec $ T (n) \ in O (\ phi ^ n) $ où $ \ phi = \ frac {1+ \ sqrt {5}} {2} $
- De plus, utiliser uniquement des images nest pas un bon style ici. Veuillez transcrire les éléments de texte – notez que vous pouvez utiliser LaTeX ici (via MathJax).
- Votre requête nest même pas fausse. La " complexité temporelle de la séquence de Fibonacci " nest pas une chose. Il y a deux choses significatives à poser ici: 1) Quelle est la croissance asymptotique de la séquence de Fibonacci (dans $ \ Theta $)? 2) Quel est le runtime asymptotique de cet algorithme de calcul des nombres de Fibonacci? – Je suppose que vous vouliez dire 2). Pour cela, nous avons quelques questions de référence , ainsi que des pour résoudre les récidives .
Réponse
Lanalyse nest pas précise bien que le résultat soit correct. Vous pouvez lécrire plus précisément en remplaçant $ = $ par $ \ le $
$ T (n) \ le c (1 + 2 + .. + 2 ^ {n-1}) $ ($ \ le $ puisque tous les niveaux nont pas le même nombre denfants, considérez le chemin le plus droitier, n diminue de 2 $ à chaque pas).
En effet, une analyse plus minutieuse peut vous aider à obtenir une limite plus serrée. mentionné dans le commentaire. Lidée est que le temps $ T (n) $ est calculé avec $ T (n-1) + T (n-2) $ de la même manière que le fibonacci réel $ F (n) $, et puisque $ F (n ) = O (\ phi ^ n) $ pour $ \ phi = (1+ \ sqrt {5}) / 2 $ comme formulaire fermé.
Ainsi $ T (n) = O (\ phi ^ n) $ qui est légèrement plus petit que $ 2 ^ n $
Commentaires
- Pour la deuxième partie, il faut tenir compte du terme de péage supplémentaire $ c $ dans la récurrence de $ T $. La récurrence pour $ F $ ne compte que les feuilles mais celle de $ T $ compte tous les nœuds. Ce nest pas toujours le cas que le nombre de feuilles domine asymptotiquement, cf. méthode darbre de récursivité.