每当调用这个函数时会产生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)。
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024