从0到n的所有斐波那契数的时间复杂度

Question

我在计算这段从0到n打印所有斐波那契数的代码的时间复杂度。根据我的计算，fib（）方法需要O（2^n），并且由于它被调用i次数，所以它出来是O（n*2^n）。然而，书上说它是O（2^n）。有人能解释一下为什么这里的时间复杂度会是O（2^n）吗？

代码如下：

void allFib(int n){
    for(int i = 0 ; i < n ; i++){
        System.out.println(i + ": " + fib(i));
    }
}

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

Answer 1

我终于从我的教授那里得到了答案，我将把它贴在这里：

他认为：你不应该只是简单地寻找从0到n迭代的for循环，而是必须通过计算步长来找到实际的计算结果。

FIB（1）需要2^1个步骤

fib（2）需要2^2个步骤

fib（3）需要2^3个步骤

..........

fib（n）需要2^n个步骤

现在添加以下内容：

2^1 2^2 2^3 ........ 2^n=2^n 1

忽略常数，它是2^n，因此时间复杂度是O（2^n）。

Answer 2

我已经找到了自己的方法来理解这本书的解决方案，希望它能帮助那些仍在挣扎的人。

假设我们现在称为allFib（n）。

由于我们有一个从0到n的for循环，将调用以下函数：

• i=0，调用fib（0）
• i=1，调用fib（1）
• i=2，调用fib（2）
• i=n-1，调用fib（n-1）

如前所述，fib（n）将采取O（2^n）=2^n步，因此，

• i=0，调用fib（0）需要2^0步

因此，allFib（n）的运行时将是

2^0 2^1 2^2 ... 2^（n-1）<代码>*

遵循我们得到的2个公式的幂和：

*=2^（n-1 1）-1=2^n-1。

因此它是O（2^n）