Question

分析下列算法的时间复杂度。麻烦也告诉一下怎样算的，谢谢！

int rec(int n)

{
if(n<=1)
return 1;
else
return rec(n-1)*rec(n-1);
}

Answer 1

每当调用这个函数时会产生2个递归分支，所以时间复杂度是O(2^n)。
n==1时，调用1次rec(1)，
n==2时，调用1次rec(2)，2次rec(1)，
n==3时，调用1次rec(3)，2次rec(2)，4次rec(1)，
以此类推，总的调用次数为2^0+2^1+2^2+...+2^(n-1)=2^n-1，
因为函数内不存在循环，T(n)=(2^n-1)*1=2^n-1，
存在正的常数c,n0使得对于任意n>=n0时有T(n)<=c*2^n，
所以这个时间复杂度是O(2^n)。