斐波那契数列的计算复杂性
我理解Big-O符号，但我不知道如何计算它的许多功能。 特别是，我一直在试图找出斐波那契序列天真版本的计算复杂性：
int Fibonacci(int n)
{
if (n <= 1)
return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
斐波纳契数列的计算复杂度是多少？它是如何计算的？
您可以对时间函数进行建模，以计算Fib(n)为计算Fib(n-1)加上计算Fib(n-2)的时间加上它们加在一起的时间（ O(1) ）的时间之和。
T(n<=1) = O(1)
T(n) = T(n-1) + T(n-2) + O(1)
你解决这个重复关系（例如使用生成函数），你会最终得到答案。
或者，您可以绘制递归树，该树具有深度n并直观地指出该函数渐近地为O(2 n ) 。 然后你可以通过归纳证明你的猜想。
基数： n = 1是显而易见的
因此，假设T(n-1) = O(2 n-1 )
T(n) = T(n-1) + T(n-2) + O(1)等于
T(n) = O(2 n-1 ) + O(2 n-2 ) + O(1) = O(2 n )
但是，正如评论所指出的那样，这不是一个严格的限制。 关于这个函数的一个有趣的事实是T（n）与Fib(n)的值渐近地相同，因为它们都被定义为
f(n) = f(n-1) + f(n-2) 。
递归树的叶子将始终返回1. Fib(n)的值是递归树中叶子返回的所有值的和，等于树叶的数量。 由于每一片叶子都将采用O（1）进行计算，因此T(n)等于Fib(n) x O(1) 。 因此，这个函数的紧束缚是斐波那契数列本身（ θ(1.6 n ) ）。 你可以通过使用上面提到的生成函数来找出这个紧密的界限。
只要问自己需要执行多少条语句才能完成F(n) 。
对于F(1) ，答案是1 （条件的第一部分）。
对于F(n) ，答案是F(n-1) + F(n-2) 。
那么，什么函数满足这些规则？ 试试（a> 1）：
an == a（n-1）+ a（n-2）
除以（n-2）：
a2 == a + 1
解决a和你得到(1+sqrt(5))/2 = 1.6180339887 ，否则被称为黄金比例。
所以需要指数时间。
麻省理工学院对这个具体问题进行了很好的讨论。 在第5页中，他们指出，如果您假设一个加法需要一个计算单位，计算Fib（N）所需的时间与Fib（N）的结果非常接近。
因此，您可以直接跳至斐波那契数列的非常接近的近似值：
Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)
并且说，因此，朴素算法的最坏情况表现是
O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))
PS：如果您想了解更多信息，可以在维基百科讨论关于第N斐波纳契数的封闭表达式。
链接地址: http://www.djcxy.com/p/6789.html