Измерение сложности для питания числа

Question

Я реализовал программу для питания числа (A ^ n), используя методику Divide и Proquer. Я реализовал две версии той же проблемы:

Версия 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) .

Я не уверен в моем выводе.

Спасибо

Answer 1

В версии 1 нет ответа, так как вы используете функцию под названием pow Что вы никогда не определяете, поэтому на самом деле нельзя сказать, что такое сложность.

В версии 2 есть избыточные расчеты, поэтому ответ зависит от того, рассматриваете ли вы эти избыточные расчеты как часть вашей сложности или нет (поскольку они могут быть легко оставлены).

Попробуйте написание версии 3 с точки зрения функции под названием square и включить определение для square

Во всех случаях вам нужны некоторые предположения о стоимости основных операций (*, /, а также +) ты используешь. Вы, вероятно, хотите предположить, что все они стоили O (1), но вы должны сделать это понятно в вашем анализе.