コンピュータプログラムの構造と解釈の講義1Bを見ながら、フィボナッチ数を計算する関数があります。講師は、時間計算量はO（fib n）であると指摘しています。これは、これまで見たことがありません。定数、線形、n + m、2次、多項式、または指数関数の複雑さに丸められるのを見てきましたが、他のO（fib n）アルゴリズムまたは他の興味深い大きなO表記を調べたり、調べたりする必要がありますか？
1 に答える
3
O(fib N)奇妙でも特別なことでもありません-それは指数関数的な複雑さとまったく同じです-それは講師がそれを詳しく説明するのに時間をかけなかったということだけです。（簡単に*バインドできますfib(N)。phi^n）
しかし、あなたは私を信じる必要はありません-あなたはMath.stackexchangeについてより良い説明があるでしょう。
*：「簡単に」とはどういう意味かを明確にします。これは、たとえばウィキペディアの記事で証明がすぐに利用できることを意味します（元々リンクを提供していた以前の回答者に感謝します）。
于 2011-01-07T07:09:59.240 に答える