Fibonacci序列的计算复杂性

Question

Fibonacci序列的计算复杂性

我理解大O表示法，但我不知道如何为许多函数计算它。特别是，我一直试图找出Fibonacci序列的简单版本的计算复杂性：

int Fibonacci(int n)
{
    if (n <= 1)
        return n;
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2);
}

斐波纳契序列的计算复杂度是多少？它是如何计算的？

Answer 1

您可以对时间函数进行建模以进行计算。Fib(n)作为计算的时间之和Fib(n-1)加上计算时间Fib(n-2)加上把它们加在一起的时间(O(1))。这是假设重复评估相同的Fib(n)采取同样的时间-即没有回忆录是有用的。T(n<=1) = O(1)T(n) = T(n-1) + T(n-2) + O(1)解决这个递归关系(例如，使用生成函数)，最终得到答案。或者，您可以绘制递归树，它将具有深度。n并直观地计算出该函数是渐近的。O(2n)..然后你可以通过归纳来证明你的猜想。基地：n = 1很明显假设T(n-1) = O(2n-1),&nbsp;因此T(n) = T(n-1) + T(n-2) + O(1)&nbsp;等于T(n) = O(2n-1) + O(2n-2) + O(1) = O(2n)然而，正如在评论中所指出的，这并不是严格的限制。关于这个函数的一个有趣的事实是，T(N)是渐近的。同作为.的价值Fib(n)因为两者都被定义为f(n) = f(n-1) + f(n-2).递归树的叶子将始终返回1。价值Fib(n)递归树中叶子返回的所有值之和，等于叶数。因为每片叶子都需要O(1)来计算，T(n)等于Fib(n) x O(1)..因此，这个函数的紧界是Fibonacci序列本身(~)θ(1.6n))。您可以像我前面提到的那样，通过使用生成函数来找出这种紧密的界限。

Answer 2

只需问自己需要执行多少个语句就可以了。F(n)完成。为F(1)，答案是1(条件的第一部分)。为F(n)，答案是F(n-1) + F(n-2).那么满足这些规则的函数是什么呢？试一试n(a>1)：an=a(n-1)+a(n-2)除以.(n-2):a2=a+1解为a你会得到(1+sqrt(5))/2 = 1.6180339887，也称为黄金比率.所以它需要指数时间。