java - 简单循环时间复杂度内的递归函数

Question

为什么在 for 循环中调用递归函数的时间复杂度是 O(2^N) 而不是 O(N 2^N)下面这段代码。基于 CTCI 一书。

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

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

Answer 1

将递归函数想象成树中的计算值。

        fib(n)
         /\
        /  \
 fib(n-1)   fib(n-2)

如果您仔细查找 n = 2，则有 3 个值需要计算，即 2^(1+1) - 1 = 3 这里的 1 是树的高度，如 2^(h+1)-1

对于n = 3，高度为h = 2

对于n = 4，高度为h = 3

对于所有 n，您需要添加所有这些: 2^2 - 1 + 2^3 - 1 + 2^4 - 1 + ....2^n - 1 -> 是 2^(n+1 )

因此你得到 O(2^n)