2

私は maxmin アルゴリズムの実装に関する複雑さを比較しており、ブルート フォース方式と分割統治方式の 2 つの方法で実装しました。1000000 と 10000000 の間の要素の 10 個の入力に対して 2 つのアルゴリズムの両方をテストした後、以下のアルゴリズムに従います。

以下のブルートフォース実装:

def maxmin1(vetor):
    max,min = vetor[0],vetor[0];
    for elem in vetor[1:]:
        if elem > max:
            max = elem
        if elem < min:
            min = elem
    return (min,max)

以下の実装を分割して征服します。

def maxmin4(vetor,inicio,fim):
    if ((fim - inicio) == 1):
        return (vetor[inicio], vetor[inicio])
    elif ((fim - inicio) == 2):
        if( vetor[inicio] < vetor[inicio+1]):
            return (vetor[inicio], vetor[inicio+1])
        else:
            return (vetor[inicio+1], vetor[inicio])
    else:
        (min_left,max_left) = maxmin4(vetor,inicio,(fim-inicio)/2 + inicio)
        (min_right,max_right) = maxmin4(vetor,(fim-inicio)/2 + inicio,fim)
        if (max_left < max_right):
            max = max_right
        else:
            max = max_left
        if (min_left < min_right):
            min = min_left
        else:
            min = min_right
    return (min,max)

そして結果：

input N     time algorithm 1 |  time algorithm 2
1000000 |   0.1299650669     |  0.6347620487 
2000000 |   0.266600132      |  1.3034451008
3000000 |   0.393116951      |  2.2436430454
4000000 |   0.5371210575     |  2.5098109245
5000000 |   0.6094739437     |  3.4496300221
6000000 |   0.8271648884     |  4.6163318157
7000000 |   1.0598180294     |  4.8950240612 
8000000 |   1.053456068      |  5.1900761128
9000000 |   1.1843969822     |  5.6422820091
10000000|   1.361964941      |  6.9290060997

最初のアルゴリズムは 2(n -1) の複雑さを持ち、2 番目のアルゴリズムは 3n/2 -2 の複雑さを持ち、理論的には最初のアルゴリズムは 2 番目のアルゴリズムよりも遅いため、最初のアルゴリズムが 2 番目のアルゴリズムよりも高速であった理由がわかりません。なぜそれが起こるのですか？

4

3 に答える 3

1

Python の再帰が Python の反復よりも速く実行されるのを見ると、非常に驚​​かれることでしょう。一度に 2 つの値を取得して、この maxmin の実装を試してください。

def minmax(seq):

    def byTwos(seq):
        # yield values from sequence two at a time
        # if an odd number of values, just return
        # the last value twice (won't hurt minmax
        # evaluation)
        seq = iter(seq)
        while 1:
            last = next(seq)
            yield last,next(seq,last)

    seqByTwos = byTwos(seq)
    # initialize minval and maxval
    a,b = next(seqByTwos,(None,None))
    if a < b:
        minval,maxval = a,b
    else:
        minval,maxval = b,a

    # now walk the rest of the sequence
    for a,b in seqByTwos:
        if a < b:
            if a < minval:
                minval = a
            if b > maxval:
                maxval = b
        else:
            if b < minval:
                minval = b
            if a > maxval:
                maxval = a
    return minval, maxval

比較をカウントする場合は、 および を実装する一連のオブジェクトを渡し、__lt__それら__gt__のメソッドにグローバル カウンターを更新させます。

于 2013-09-18T19:22:34.970 に答える