0

分割統治法を使用して数値 (a^n) を累乗するプログラムを実装しました。私は同じ問題の2つのバージョンを実装しました:

バージョン 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)ます。

私の結論についてはよくわかりません。

ありがとう

4

1 に答える 1

1

バージョン 1 では、pow定義しないで呼び出される関数を使用するため、答えがありません。したがって、複雑さが何であるかを実際に言うことはできません。

バージョン 2 には冗長な計算があるため、その答えは、それらの冗長な計算を複雑さの一部と見なすかどうかによって異なります (簡単に省略できるため)。

呼び出された関数の観点からバージョン 3 を書きsquare、次の定義を含めてみてください。square

いずれの場合も、使用する基本操作 ( *、/、および+) のコストについていくつかの仮定が必要です。おそらく、すべてのコストが O(1) であると想定したいでしょうが、分析ではそれを明確にする必要があります。

于 2010-12-06T07:57:12.663 に答える