计算复杂的斐波那契数列的

StackOverflow https://stackoverflow.com/questions/360748

题

我了解大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)）的时间。这是假设同一Fib(n)的重复评价采取相同的时间 - 即，没有记忆化是使用

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)。因此，紧绑定此函数是Fibonacci序列本身（〜θ(1.6 n )）。你能发现这通过如我已经如上所述使用生成函数紧约束。

其他提示

问问你自己有多少语句需要执行的F(n)完成。

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

有关F(n)，答案是F(n-1) + F(n-2)。

那么，什么功能满足这些规则？尝试名词（A> 1）：

一个名词 ==一个（N-1） +一（N-2）功能

通过除以通过第（n-2）：

一个 2 ==一个+ 1

求解a，你会得到(1+sqrt(5))/2 = 1.6180339887，否则被称为黄金比例

因此，需要指数时间。

有href="http://courses.csail.mit.edu/6.01/spring07/lectures/lecture4.pdf"在麻省理工学院特定问题这。第5页，他们做的是，如果你假设一个除了需要一个计算单元，计算蛋白原（N）所需的时间点是非常密切相关的纤维蛋白原（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 Fibonacci数的形式表达在维基百科，如果您想了解更多信息。

我同意pgaur和rickerbh，递归斐波纳契的复杂度为O（2 ^ N）。

我得出了同样的结论相当简单，但我认为仍然有效的推理。

首先，它是所有关于找出多少次递归函数斐波纳契（F（）从现在起）计算第n个斐波纳契数时被调用。如果它得到的序列中每个数字一度被称为0到n，那么我们就为O（n），如果它被调用n次的每个数字，然后我们得到O（N * N），或者为O（n ^ 2）等。

所以，当F（）被调用用于数量为n，的次数F（）称为对于给定数目0和之间n-1个生长在我们接近0。

作为第一个印象，在我看来，如果我们把它放在一个可视化的方式，每次F（）被调用时，某个数字绘制单元，湿获得一种金字塔形的（也就是说，如果我们水平居中单元）。是这样的：

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

现在，问题是，如何快速这金字塔放大正生长的基

让我们实际情况下，例如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）线现在在长度上相等。这意味着，总次数F（）被调用，当n = 6是2×32 = 64 = 2 ^ 6

现在，在复杂性方面：

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

可以展开，并有一个可视化

     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的上端（如在其他评论中所指出）。和递归实现的一个有趣的事实是，它具有结合到纤维蛋白原（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）= T（N-1）+ T（N-2）+ O可更好地估计（1 ） 注意，每个步骤花费O（1），这意味着恒定的时间，因为它只有一个比较在检查的n值如果 block.Recursion树看起来像

          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)

允许在我的特定值说，树端部，这种情况下将是当n-1 = 1，因此，I = N-1，这意味着树的高度是n-1个。 现在让我们看到每个在tree.Note 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) ]的顺序。

http://www.ics.uci.edu/~eppstein /161/960109.html

<强>时间（n）= 3F（N） - 2

天真的递归版本的斐波那契数指数是通过设计，由于重复计算：

在根你是计算：

F(n)取决于F(n-1)和F(n-2)

F(n-1)取决于F(n-2)再次和F(n-3)

F(n-2)，取决于F(n-3)再次和F(n-4)

然后你都具有在各级别2recursive calls是浪费了大量的数据在计算，该时间的功能将是这样的：

T(n)=T(n-1)+T(n-2)+C，C恒

T(n-1)=T(n-2)+T(n-3)>T(n-2)然后

T(n)>2*T(n-2)

...

T(n)>2^(n/2)*T(1)=O(2^(n/2))

这只是一个下限，对于目的分析应该是足够的，但实时功能是一个因素的一个常由相同的斐波那契式和 封闭的形式 是已知的被指数的黄金比例。

此外，您可以找到优化版本的斐波那契使用动态规划是这样的：

static int fib(int n)
{
    /* memory */
    int f[] = new int[n+1];
    int i;

    /* Init */
    f[0] = 0;
    f[1] = 1;

    /* Fill */
    for (i = 2; i <= n; i++)
    {
        f[i] = f[i-1] + f[i-2];
    }

    return f[n];
}

优化的和做的只有 n 步骤，但是也指数。

成本功能的定义是从输入的小数量的步骤来解决这个问题。当你看到的动态版本的斐波那契(n 步骤来计算表)或最简单的算法知道如果一个数字是总理(sqrt(n) 分析的有效的除数的数量)。你可能认为这些算法 O(n) 或 O(sqrt(n)) 但这是不正确的，原因如下：输入你的算法是一个数字： n, 使用的二进制表示的尺寸的输入一个整数 n 是 log2(n) 然后做一个变量变化

m = log2(n) // your real input size

让我们找出这些步骤作为一个输入功能的尺寸

m = log2(n)
2^m = 2^log2(n) = n

然后成本的算法函数的尺寸的输入是：

T(m) = n steps = 2^m steps

这就是为什么成本是一个指数。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top