这个程序的时间复杂度是多少

Question

此代码计算a^b。。但我不确定它的复杂性

def powerFunc(a,b):
if b==1:
return a
elif b==0:
return 1
else:
return a*powerFunc(a,b-1)
a=int(input())
b=int(input())
print(powerFunc(a,b))

Answer 1

使用递归函数，您可以从写下递归关系开始：

T(a,0) = O(1)
T(a,1) = O(1)
T(a,b) = T(a,b-1) + O(1) for b > 1

这是一个非常简单的方程，具有解

T(a,b) = O(b)

空间复杂度也是O(b(，因为函数不是尾递归的。