我使用分治技术实现了一个为数字 (a^n) 供电的程序。我实现了相同问题的两个版本：
版本 1：
def input_params():
a=input('Input \'a\' & \'n\' for a^n:')
n=input('')
result=power(a,n)
print (result)
def power(a,n):
if n<=1:
return a
elif n%2==0:
return pow(power(a,n/2),2)
else:
return pow(power(a,(n-1)/2),2)*a
if __name__ == "__main__":
input_params()
版本 2：
def input_params():
a=input('Input \'a\' & \'n\' for a^n:')
n=input('')
result=power(a,n)
print (result)
def power(a,n):
if n<=1:
return a
elif n%2==0:
return power(a,n/2)*power(a,n/2)
else:
return power(a,(n-1)/2)*power(a,(n-1)/2)*a
if __name__ == "__main__":
input_params()
版本 3：
def input_params():
a=input('Input \'a\' & \'n\' for a^n:')
n=input('')
result=power(a,n)
print (result)
def power(a,n):
if n<=1:
return a
elif n%2==0:
return square(power(a,n/2))
else:
return square(power(a,(n-1)/2))*a
def square(num):
return num*num
if __name__ == "__main__":
input_params()
Q1：以上哪个版本的复杂度是θ(lg n)？
Q2：如果版本 2 的复杂度为θ(lg n)，为什么？因为虽然第 2 版中的问题大小是除以 2，但子问题的数量也是 2，所以我觉得第 2 版会按θ(nlg n).
我不确定我的结论。
谢谢