分析下列算法的时间复杂度。麻烦也告诉一下怎样算的，谢谢！7
发布网友
发布时间：2023-11-22 18:51
共1个回答
热心网友
时间：2024-12-13 16:18
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)。
