在观看计算机程序的结构和解释的讲座 1B 时，有一个计算斐波那契数的函数。讲师指出时间复杂度为 O(fib n) - 我以前从未见过。我已经看到它四舍五入为常数、线性、n+m、二次、多项式或指数复杂度，但是否还有其他 O(fib n) 算法或其他有趣的大 O 表示法值得研究或研究？
问问题
799 次
1 回答
3
O(fib N)没有什么奇怪或特别的——它与指数复杂性完全一样——只是讲师没有花时间把它拼出来。（你可以很容易地*绑定fib(N)。phi^n）
不过你不必相信我——你会对Math.stackexchange有更好的解释。
*：我将澄清我所说的“容易”是什么意思——这意味着证明是现成的，例如在那篇维基百科文章中（感谢最初提供链接的先前回答者）。
于 2011-01-07T07:09:59.240 回答