我计算了这个代码的时间复杂度，这个代码打印了从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);
}
我已经找到了自己的方法来理解这本书的解决方案，希望它能帮助那些仍在挣扎的人。
想象一下，我们现在调用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(。*
遵循我们的2次幂和公式：
*=2^(n-1+1(-1=2^n-1。
因此它是O(2^n(
我终于从教授那里得到了答案，我会把它发布在这里：
根据他的说法：你不应该只是简单地寻找从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(。