big-o - 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 绑定(bind)。)

不过你不必相信我——你会对 Math.stackexchange 有更好的解释。 .

*:我将澄清我所说的“容易”是什么意思——这意味着证明很容易获得，例如在 that wikipedia article 中。 (感谢最初提供链接的先前回答者)。