Fibonacci序列的计算复杂性-Java 学习之路

271

我理解Big-O表示法，但我不知道如何为许多函数计算它 . 特别是，我一直试图弄清楚Fibonacci序列的幼稚版本的计算复杂性：

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

Fibonacci序列的计算复杂度是多少？它是如何计算的？

12 回答

311

您可以将时间函数建模为 Fib(n) ，作为计算 Fib(n-1) 的时间加上计算 Fib(n-2) 的时间加上将它们加在一起的时间（ O(1) ） .

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）渐近 the same 作为 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 ) ） . 你可以通过使用我上面提到的生成函数来找出这个紧密的界限 .

回复于 2024-04-27T09:40:42+08:00
25

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

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

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

那么什么功能满足这些规则呢？试试（a> 1）：

an == a（n-1）a（n-2）

除以（n-2）：

a2 == a 1

解决 a 并得到 (1+sqrt(5))/2 = 1.6180339887 ，也称为golden ratio .

所以它需要指数时间 .

回复于 2024-04-27T09:40:42+08:00
0
对这个specific problem over at MIT进行了非常好的讨论 . 在第5页，他们指出，如果你假设一个加法需要一个计算单位，那么计算Fib（N）所需的时间与Fib（N）的结果密切相关 .

因此，您可以直接跳到Fibonacci系列的非常接近的近似值：
```
Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)
```
并且因此说，天真算法的最坏情况表现是
```
O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))
```
PS：如果您想了解更多信息，请在维基百科上讨论closed form expression of the Nth Fibonacci number .
回复于 2024-04-27T09:40:42+08:00
2
我同意pgaur和rickerbh，recursive-fibonacci的复杂性是O（2 ^ n） .

我以相当简单的方式得出了相同的结论，但我认为仍然是有效的推理 .

首先，它是关于计算在计算第N个斐波纳契数时调用递归的斐波纳契函数（从现在开始的F（））的次数 . 如果在序列0到n中每个数字调用一次，那么我们有O（n），如果每个数字被调用n次，那么我们得到O（n * n）或O（n ^ 2），等等 .

因此，当为数字n调用F（）时，对于0和n-1之间的给定数字，调用F（）的次数随着接近0而增长 .

作为第一印象，在我看来，如果我们以可视方式放置它，每次为一个给定数字调用F（）时绘制一个单位，wet得到一种金字塔形状（也就是说，如果我们水平居中单位）） . 像这样的东西：
```
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时，调用F（）的总次数是2x32 = 64 = 2 ^ 6 .

现在，就复杂性而言：
```
O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)
```
回复于 2024-04-27T09:40:42+08:00

您可以扩展它并进行可视化

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)

回复于 2024-04-27T09:40:42+08:00

1
它的下端由 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)
```
如果你愿意，可以使用closed form进一步减少紧密限制 .
回复于 2024-04-27T09:40:42+08:00
9
证明答案是好的，但我总是需要手工做几次迭代才能真正说服自己 . 所以我在我的白板上画了一个小的调用树，并开始计算节点 . 我将计数分为总节点，叶节点和内部节点 . 这是我得到的：
```
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)) .
回复于 2024-04-27T09:40:42+08:00
-4
好吧，据我说它是 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) ] 的顺序 .
回复于 2024-04-27T09:40:42+08:00
28

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

time(n) = 3F(n) - 2

回复于 2024-04-27T09:40:42+08:00
8
通过绘制递归树可以更好地估计递归算法的时间复杂度 . 在这种情况下，绘制递归树的递归关系将是T（n）= T（n-1）T（n-2）O（1）注意每一步取O（1）意味着恒定的时间，因为它在 if block中只检查n的值，而且只有一个比较.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)
```
让我们说在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)
回复于 2024-04-27T09:40:42+08:00
12
由于计算中的重复，Fibonacci的朴素递归版本是指数式的：

你在计算根源：

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）

然后你在每个级别进行2次递归调用，这些调用在计算中浪费了大量数据，时间函数将如下所示：

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））

这只是一个下限，为了你的分析目的应该足够，但实时函数是一个常数的因子乘以相同的斐波纳契公式，并且已知closed form是黄金比率的指数 .

此外，您可以使用动态编程找到Fibonacci的优化版本，如下所示：
```
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 步骤，但也是指数 .

成本函数是从输入大小到解决问题的步骤数定义的 . 当你看到Fibonacci的动态版本（计算表的 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
```
这就是成本是指数的原因 .
回复于 2024-04-27T09:40:42+08:00

110

这样做更好：

unsigned int Fib(unsigned int n)
{
    // first Fibonaci number is Fib(0)
    // second one is Fib(1) and so on

    // unsigned int m;  // m + current_n = original_n
    unsigned int a = 1; // Fib(m)
    unsigned int b = 0; // Fib(m-1)
    unsigned int c = 0; // Fib(m-2)

    while (n--)
    {
        c = b;
        b = a;
        a = b+c;
    }

    return a;
}

回复于 2024-04-27T09:40:42+08:00

Fibonacci序列的计算复杂性

12 回答

相关问题