O（fib n）复杂性算法？
在观看计算机程序结构和解释讲座1B的同时，还有一个计算斐波纳契数字的函数。 讲师指出时间复杂度为O（fib n） - 我以前从未见过。 我已经看到它被舍入为常数，线性，n + m，二次，多项式或指数复杂度，但是是否还有其他O（fib n）算法或其他有趣的大O符号应该被观察或研究？
O(fib N)没有什么奇怪或特殊之处 - 它与指数复杂性完全相同 - 只是讲师没有花时间把它拼出来。 （你可以很容易地*绑定fib(N)与phi^n 。）
你不必相信我 - 你会对Math.stackexchange有更好的解释。
*：我会澄清我的意思是“容易” - 这意味着证明是容易获得的，例如在该维基百科文章中（感谢先前答复者最初提供的链接）。
链接地址: http://www.djcxy.com/p/39911.html