O（fib n）複雑アルゴリズム？

Question

lecture 1B of the Structure and Interpretation of Computer Programsを見て、フィボナッチ数を計算する関数があります。講師は時間の複雑さがO（fib n）であることを指摘しています。私はそれが定数、線形、n + m、二次、多項式、または指数複雑さに丸められたのを見ましたが、他のO（fib n）アルゴリズムや他の興味深い大きなO表記があります。

Answer 1

O(fib N)は何も変わっていません。指数関数的な複雑さとまったく同じものです。講師がそれを綴る時間がかかりませんでした。 （fib(N)をphi^nと簡単に結びつけることができます）

Math.stackexchangeについては、私には分かりません。

*：「簡単に」という意味を明確にしています。つまり、その証拠がすぐに利用可能であることを意味します。たとえば、that wikipedia articleなどです（以前の回答者のおかげで）。