我知道大o符号,但我不知道如何计算它的许多函数。特别是,我一直在试图弄清楚朴素版斐波那契数列的计算复杂度:

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

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


当前回答

我同意pgaur和rickerbh的观点,递归-fibonacci的复杂度是O(2^n)。

我通过一个相当简单但我相信仍然有效的推理得出了同样的结论。

首先,这完全是关于计算第n个斐波那契数时调用多少次递归斐波那契函数(F()从现在开始)。如果它在0到n的数列中被调用一次,那么我们有O(n),如果它对每个数字被调用n次,那么我们得到O(n*n)或O(n²),以此类推。

因此,当对一个数字n调用F()时,对一个给定的0到n-1之间的数字调用F()的次数随着趋近于0而增加。

作为第一印象,在我看来,如果我们把它放在视觉上,每次绘制一个单位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(1)和F(0)线现在长度相等。这意味着,当n=6 = 2x32=64=2^6时,total乘以F()被调用。

现在,说到复杂性:

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

其他回答

它的下端以2^(n/2)为界,上端以2^n为界(如其他注释中所述)。这个递归实现的一个有趣的事实是它本身有一个紧密的Fib(n)渐近界。这些事实可以总结为:

T(n) = Ω(2^(n/2))  (lower bound)
T(n) = O(2^n)   (upper bound)
T(n) = Θ(Fib(n)) (tight bound)

如果你愿意,可以用它的封闭形式进一步简化紧边界。

通过绘制函数调用图来计算很简单。简单地为n的每个值添加函数调用,看看这个数字是如何增长的。

大O是O(Z^n), Z是黄金比例,约为1.62。

当我们增加n时,列奥纳多数和斐波那契数都接近这个比率。

与其他大O问题不同,输入中没有可变性,算法和算法的实现都是明确定义的。

不需要一堆复杂的数学。简单地画出下面的函数调用,并将函数与数字匹配。

如果你熟悉黄金比例你就能认出来。

这个答案比公认的f(n) = 2^n的答案更正确。永远不会。它会趋于f(n) = golden_ratio^n。

2 (2 -> 1, 0)

4 (3 -> 2, 1) (2 -> 1, 0)

8 (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)


14 (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)

            (3 -> 2, 1) (2 -> 1, 0)

22 (6 -> 5, 4)
            (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)

                        (3 -> 2, 1) (2 -> 1, 0)

            (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)

将计算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)。因此,这个函数的紧界是斐波那契数列本身(~θ(1.6n))。你可以使用我上面提到的生成函数来找到这个紧边界。

证明答案很好,但我总是不得不手工做一些迭代来真正说服自己。所以我在白板上画了一个小的调用树,并开始计算节点。我将计数分为总节点、叶节点和内部节点。以下是我得到的答案:

IN | OUT | TOT | LEAF | INT
 1 |   1 |   1 |   1  |   0
 2 |   1 |   1 |   1  |   0
 3 |   2 |   3 |   2  |   1
 4 |   3 |   5 |   3  |   2
 5 |   5 |   9 |   5  |   4
 6 |   8 |  15 |   8  |   7
 7 |  13 |  25 |  13  |  12
 8 |  21 |  41 |  21  |  20
 9 |  34 |  67 |  34  |  33
10 |  55 | 109 |  55  |  54

显而易见的是,叶节点的数量是fib(n)经过几次迭代才发现,内部节点的数量是fib(n) - 1。因此节点总数为2 * fib(n) - 1。

由于在对计算复杂度进行分类时去掉了系数,最终答案是θ(fib(n))。

好吧,根据我的说法,它是O(2^n),因为在这个函数中,只有递归花费了相当多的时间(分治)。我们看到,上面的函数将在树中继续存在,直到叶子趋近于F(n-(n-1))级,即F(1)。因此,当我们在这里记下树的每个深度处遇到的时间复杂度时,求和级数为:

1+2+4+.......(n-1)
= 1((2^n)-1)/(2-1)
=2^n -1

它是2^n的O(2^n)阶。