フィボナッチ数列の時間計算量を見つける[クローズ]

クローズ。この質問には、詳細または明確さが必要です。現在、回答を受け付けていません。

あなたの質問には、元の問題に対する完全な回答がすでに含まれていますが、この回答についての質問はありません。したがって、"はい/いいえ"の回答のみが残り、あなたも将来の訪問者も助けません。関連するメタディスカッションこちらとこちらを読み、それに応じて質問を調整してください。あなたの答えの単一の要素についての特定の質問を定式化することによって、あなたは不確かです。一般的なフィードバックが必要な場合は、コンピュータサイエンスチャットにアクセスしてください。
@DavidRicherbyでは、私を見ないでください。可能であれば、答えて答えてください。質問を手伝うのではなく、質問の誤りを誰もが見つけ始めるまで、私はこのサイトを愛していました。
あなたが尋ねようとしていることから、はい$ T（n）$は$になりますO（2 ^ n）$ですが、' dの上限は$ T（n）\ in O（\ phi ^ n）$で、$ \ phi = \ fracです。 {1 + \ sqrt {5}} {2} $
また、ここでは画像だけを使用するのは適切なスタイルではありません。テキスト要素を書き写してください-ここで（MathJax経由で）LaTeXを使用できることに注意してください。
クエリは間違っていません。 "フィボナッチ数列の時間計算量"は問題ではありません。ここで質問する2つの意味のあることがあります：1）フィボナッチ数列（$ \ Theta $内）の漸近的成長は何ですか？ 2）フィボナッチ数を計算するこのアルゴリズムの漸近実行時間はどれくらいですか？ -2）という意味だと思います。そのために、参照用の質問がいくつかあります。また、再発を解決するためのもあります。

回答

結果は正しいのですが、分析は正確ではありません。 $ = $を$ \ le $

$ T（n）\ le c（1 + 2 + .. + 2 ^ {n-1}）$（$に置き換えることで、より正確に記述できます。 \ le $すべてのレベルに同じ数の子があるわけではないので、最も右利きのパスを検討してください。nはステップごとに$ 2 $ずつ減少します。

実際、より注意深く分析すると、コメントに記載されています。アイデアは、時間$ T（n）$が実際のフィボナッチ$ F（n）$と同じ方法で、$ F（n-1）+ T（n-2）$で計算されるということです。）= O（\ phi ^ n）$ for $ \ phi =（1+ \ sqrt {5}）/ 2 $閉じた形として。

したがって、$ T（n）= O（\ phi ^ n）$は、$ 2 ^ n $よりわずかに小さいです

2番目の部分では、$ T $の繰り返しで追加の料金期間$ c $に注意する必要があります。 $ F $の漸化式は葉のみをカウントしますが、$ T $の1つはすべてのノードをカウントします。葉の数が漸近的に支配的であるとは限りません。再帰ツリーメソッド。

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル