algorithm - 函数的复杂度是多少 f(n) = f(n-1)+f(n-2)+f(n-3)+...+1

Question

计算 n 的这个函数的时间复杂度是多少。

int rec(int n)
{
    if (n<=1) {
        return n ;
    }
    int i;
    int sum=0;
    for (i=1; i<n; i++) {
       sum=sum+rec(i); 
    }
    return sum ;
}

Answer 1

好吧，让我们打破这个

 (1)        f(n) = f(n-1) + f(n-2) + ... f(1) + 1

然而，

 (2)        f(n-1) = f(n-2) + ... f(1) + 1

所以将（2）插入（1）给出

 (3)        f(n) = f(n-1) + f(n-1) = 2 f(n-1)

并且 f(2) = 1，所以这显然是 2 ⁿ（详情：无法计算出这种递归的复杂性）。好吧，实际上是 2 ^n-1但在大 O 中，这并不重要，因为^-1与 /2 相同。