Я реализовал программу для питания числа (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 будет расти в порядке θ(nlg n).
Я не уверен в своем заключении.
Спасибо