geschlossen . Diese Frage benötigt Details oder Klarheit . Derzeit werden keine Antworten akzeptiert.
Kommentare
- Ihre Frage enthält bereits eine vollständige Antwort auf das ursprüngliche Problem, aber keine Frage zu dieser Antwort. Daher dürfen nur " Ja / Nein " Antworten übrig bleiben, die weder Ihnen noch zukünftigen Besuchern helfen. Bitte lesen Sie verwandte Metadiskussionen hier und hier und passen Sie Ihre Frage entsprechend an, z. Wenn Sie eine bestimmte Frage zu einem einzelnen Element Ihrer Antwort formulieren, sind Sie sich nicht sicher. Wenn Sie nur allgemeines Feedback wünschen, können Sie uns gerne in Informatik-Chat besuchen.
- @DavidRicherby Dann versuchen Sie nicht, meine anzusehen antworte und antworte, wenn du kannst. Ich habe diese Seite geliebt, bis alle anfingen, Fehler bei den gestellten Fragen zu finden, anstatt demjenigen bei der Frage zu helfen.
- Nach dem, was Sie meiner Meinung nach zu fragen versuchen, wäre $ T (n) $ in $ O (2 ^ n) $, aber Sie ' hätten eine engere Obergrenze mit $ T (n) \ in O (\ phi ^ n) $, wobei $ \ phi = \ frac {1+ \ sqrt {5}} {2} $
- Auch die Verwendung von Bildern allein ist hier kein guter Stil. Bitte transkribieren Sie die Textelemente – beachten Sie, dass Sie LaTeX hier verwenden können (über MathJax).
- Ihre Abfrage ist nicht einmal falsch. Die " Zeitkomplexität der Fibonacci-Sequenz " ist keine Sache. Hier sind zwei wichtige Fragen zu stellen: 1) Wie wächst die Fibonacci-Sequenz asymptotisch (in $ \ Theta $)? 2) Was ist die asymptotische Laufzeit dieses Algorithmus zur Berechnung der Fibonacci-Zahlen? – Ich denke du meintest 2). Dafür haben wir ein paar Referenzfragen und auch zum Lösen von Wiederholungen .
Antwort
Die Analyse ist nicht genau, obwohl das Ergebnis korrekt ist. Sie können es genauer schreiben, indem Sie $ = $ durch $ \ le $
$ T (n) \ le c (1 + 2 + .. + 2 ^ {n-1}) $ ($) ersetzen \ le $ da nicht alle Ebenen die gleiche Anzahl von Kindern haben, betrachten Sie den Pfad für Rechtshänder, n verringert sich bei jedem Schritt um $ 2 $.
In der Tat kann eine sorgfältigere Analyse zu einer engeren Bindung führen als im Kommentar erwähnt. Die Idee ist, dass die Zeit $ T (n) $ mit $ T (n-1) + T (n-2) $ genauso berechnet wird wie die tatsächlichen Fibonacci $ F (n) $ und seit $ F (n ) = O (\ phi ^ n) $ für $ \ phi = (1+ \ sqrt {5}) / 2 $ als geschlossene Form.
Somit ist $ T (n) = O (\ phi ^ n) $, was etwas kleiner als $ 2 ^ n $ ist.
Kommentare
- Für den zweiten Teil muss man den zusätzlichen Mautbegriff $ c $ bei der Wiederholung von $ T $ berücksichtigen. Die Wiederholung für $ F $ zählt nur Blätter, aber die von $ T $ zählt alle Knoten. Es ist nicht immer so, dass die Anzahl der Blätter asymptotisch dominiert, vgl. Rekursionsbaummethode.