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

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

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


当前回答

你可以展开它,有一个可视化

     T(n) = T(n-1) + T(n-2) <
     T(n-1) + T(n-1) 

     = 2*T(n-1)   
     = 2*2*T(n-2)
     = 2*2*2*T(n-3)
     ....
     = 2^i*T(n-i)
     ...
     ==> 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)

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

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

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))。

通过绘制递归树可以更好地估计递归算法的时间复杂度,在这种情况下,绘制递归树的递归关系为T(n-1) =T(n- 2)+O(1) 注意,每一步花费O(1)意味着常数时间,因为它只做了一次比较来检查if块中的n值。递归树是这样的

          n
   (n-1)      (n-2)
(n-2)(n-3) (n-3)(n-4) ...so on

这里假设上面树的每一层都用i表示 因此,

i
0                        n
1            (n-1)                 (n-2)
2        (n-2)    (n-3)      (n-3)     (n-4)
3   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)

假设在特定的i值处,树就结束了,也就是当n-i=1时,因此i=n-1,也就是说树的高度是n-1。 现在让我们看看树中n层中的每一层做了多少工作。注意,按照递归关系,每一步花费O(1)时间。

2^0=1                        n
2^1=2            (n-1)                 (n-2)
2^2=4        (n-2)    (n-3)      (n-3)     (n-4)
2^3=8   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)    ..so on
2^i for ith level

因为i=n-1是树的高度,所以每一层所做的功为

i work
1 2^1
2 2^2
3 2^3..so on

因此,所做的总功将是每一层所做的功的总和,因此它将是2^0+2^1+2^2+2^3…+2^(n-1),因为i=n-1。 通过几何级数,这个和是2^n,因此总时间复杂度是O(2^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)阶。

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

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

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

那么什么函数满足这些规则呢?试试an (a > 1):

==地理==根据美国人口普查,该镇总面积为,其中土地和(1.1%)水。

再除以a(n-2)

A2 == a + 1

解出a,你得到(1+根号(5))/2 = 1.6180339887,也就是黄金比例。

所以需要指数级的时间。