o（fib n）複雑さのアルゴリズム？

Question

見ている間 コンピュータープログラムの構造と解釈の講義1B, 、フィボナッチ数を計算する関数があります。講師は、時間の複雑さはo（fib n）であると指摘しています。私はそれが一定、線形、n+m、二次、多項式、または指数関数的な複雑さに丸くなっているのを見ましたが、他のO（fib n）アルゴリズムまたは他の興味深い大きなo表記を見たり研究するべきですか？

Answer 1

O(fib N) 奇妙なことも特別なこともありません - それは指数関数的な複雑さとまったく同じです - それは講師がそれを綴るのに時間をかけなかったということです。 （簡単に*バインドできます fib(N) と phi^n.)

あなたは私を信じる必要はありません - あなたはより良い説明をするでしょう Math.StackexChange.

*：「簡単に」という意味を明確にします - それは、例えば、証明が容易に利用できることを意味します。 そのウィキペディアの記事 （元々それにリンクを与えた以前の回答者に感謝します）。