数字を動かすための複雑さの測定

Question

分割と征服のテクニックを使って数字（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() 

私は同じ問題の2つのバージョンを実装しました

Q1：上記のバージョンのどれが複雑度がθ(lg n)になっていますか？

Q2：バージョン2の複雑さがθ(lg n)の場合、その理由は何ですか？バージョン2の問題サイズは2で割っていますが、副問題の数も2であるため、バージョン2はθ(nlg n)の順に大きくなると感じています。

私の結論はわかりません。あなたが定義することはありませんpowと呼ばれる機能を使用するように、1つは本当に複雑であるものを言うことができないので、

おかげバージョン1では

Answer 1

は、何の答えは、ありません。

バージョン2では、冗長な計算が行われるため、その冗長な計算を複雑さの一部として考慮するかどうかによって決まります（簡単に除外できるため）。

はsquareと呼ばれる機能の面でバージョン3を書いてみて、あなたが使用して基本的な操作（*、/、そして+）のコストに関するいくつかの仮定を必要とするすべての場合においてsquare

の定義が含まれています。あなたはおそらくそれらすべてがO（1）であると仮定したいと思うかもしれませんが、あなたの分析でそれを明確にすべきです。