time-complexity - 从 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

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

假设我们现在调用 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 步
• i = 1，调用 fib(1) 需要 2^1 步
• i = 2，调用 fib(2) 需要 2^2 步
• ...
• i = n-1，调用 fib(n-1) 需要 2^(n-1) 步

因此，allFib(n) 的运行时间将为

2^0 + 2^1 + 2^2 + ... + 2^(n-1)。 *

关注sum of powers of 2 formula我们有:

* = 2^(n-1+1) - 1 = 2^n - 1。

因此它是 O(2^n)