函数的复杂度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相同.