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.

*：我会澄清我所说的“轻松” - 这意味着证明很容易获得，例如 这篇Wikipedia文章 （感谢最初给出链接的先前答案器）。