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（感謝先前回答者最初給出鏈接）。