Fibonacci序列的计算复杂性

Question

我理解Big-O符号，但我不知道如何为许多函数计算它。特别是，我一直在试图找出斐波那契序列的原始版本的计算复杂性：

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

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

Answer 1

只要问问自己需要执行多少条语句才能完成F(n)。

对于F(1)，答案是1（条件的第一部分）。

对于F(n)，答案是F(n-1) + F(n-2)。

那么什么函数满足这些规则呢？尝试aⁿ（a>；1）：

aⁿ==a^（n-1）+a^（n-2）

除以a^（n-2）：

a²==a+1

求解a，得到(1+sqrt(5))/2 = 1.6180339887，也就是golden ratio。

所以它需要指数时间。

Answer 2

我同意pgaur和rickerbh，递归fibonacci的复杂性是O（2^n）。

我得出了同样的结论，但我相信仍然是合理的推理。

首先，要弄清楚在计算第n个斐波那契数时，递归斐波那契函数（F（）从现在开始）被调用了多少次。如果在0到n的序列中每个数字调用一次，那么我们有O（n），如果每个数字调用n次，那么我们得到O（n*n），或者O（n^2），依此类推。

因此，当对一个数字n调用F（）时，当我们接近0时，对一个介于0和n-1之间的给定数字调用F（）的次数会增加。

作为第一印象，在我看来，如果我们把它放在一个视觉的方式，每次为一个给定的数字调用F（）绘制一个单位，就会得到一种金字塔形状（也就是说，如果我们将单位水平居中）。像这样的：

n              *
n-1            **
n-2           ****  
...
2           ***********
1       ******************
0    ***************************

现在，问题是，这个金字塔的底部随着n的增长有多快？

让我们以一个真实的案例为例，例如F（6）

F(6)                 *  <-- only once
F(5)                 *  <-- only once too
F(4)                 ** 
F(3)                ****
F(2)              ********
F(1)          ****************           <-- 16
F(0)  ********************************    <-- 32

我们看到F（0）被调用了32次，也就是2^5，对于这个例子来说是2^（n-1）。

现在，我们想知道F（x）被调用了多少次，我们可以看到F（0）被调用的次数只是其中的一部分。

如果我们把所有的＊从F（6）线移到F（2）线，我们看到F（1）线和F（0）线在长度上是相等的。也就是说，当n=6是2x32=64=2^6时，调用F（）的总次数。

现在，就复杂性而言：

O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)

Answer 3

将计算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)，因此

T(n) = T(n-1) + T(n-2) + O(1)等于

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)）。您可以通过使用我前面提到的生成函数来找到这个紧边界。