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

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)

space 复杂度也是 O(b)，因为该函数不是尾递归的。