0

I want to find the maximum element in an array in O(log N) time using divide and conquer. I found a working code at planet-source-code. I translated it into Python as follows:

def largest(arr,i,j):
    global max1
    global max2
    if i == j:
        max1 = arr[i]
    else:
        if i == j-1:
           max1 = arr[i] if arr[i] > arr[j] else arr[j]
        else:
              mid = (i+j)/2
              largest(arr,i,mid)
              max2 = max1
              largest(arr,mid+1,j)
              if max2 > max1:
             max1 = max2

When I use an array [98,5,4,3,2,76,78,92], and call the code as

max1 = arr[0]
largest(arr,1,8)

I am getting a out-of-bound list index error. However the C code returns the correct result 98. Can anyone spot what error am I doing?

4

2 に答える 2

3

max一般的なソートされていない配列の場合、O(n) 時間より短い時間で を見つけることはできません。非常に些細な証拠: O(n) 時間未満でそれを行うと、十分に大きな配列の場合、すべての要素を検査するのに十分な時間がありません。したがって、敵対者は、チェックしない要素に最大値を設定し、アルゴリズムを不正確にする可能性があります。

元のコードが優れているのは、2n 未満の比較を使用して最大値と最小値の両方を同時に見つけることです (単純な実装ではそうです)。2 つの要素がある場合に比較を 1 回しか実行しないため、約 1.5n の比較を使用します。最大値を見つけるためだけに使用しても何のメリットmax(arr)もありません。代わりに Python で使用する方がよいでしょう (関数呼び出しのオーバーヘッドがないため、より高速になります)。

元のコードは値をa[1]throughに格納しますがa[n]、これには size の配列が必要n+1です。したがって、最初の位置にダミー要素を配置する必要があります。

しかし、もっと問題なのは、あなたの翻訳が間違っていることです。オリジナルは、グローバルを使用して複数の値を返す (これは信じられないほどハックな方法です) と、ローカル変数を使用して古いグローバルを保存します。両方max1をmax2グローバルにするため、関数はとにかく正しい答えを生成しません。

Python への正しい変換では、タプルを使用して複数の値を直接返すことができます。

def minmax(arr, i, j):
    if i==j:
        return arr[i], arr[i]
    elif i==j-1:
        if arr[i] < arr[j]:
            return arr[i], arr[j]
        else:
            return arr[j], arr[i]
    else:
        mid = (i+j)//2
        min1, max1 = minmax(arr, i, mid)
        min2, max2 = minmax(arr, mid+1, j)
        if min2 < min1: min1 = min2
        if max2 > max1: max1 = max2
        return min1, max1
于 2012-10-14T16:44:19.350 に答える
1

あなたは関数呼び出しを持つことになります

largest(arr, 7,8)

次に、コード

max1 = arr[i] if arr[i] > arr[j] else arr[j]

Pythonは1〜8ではなく0〜7のベクトルを列挙するため、範囲外のarr [j] =arr[8]にインデックスを付けようとします。

ところで、O（log N）アルゴリズムを使用しているとは思いません。最大の要素を見つけるには、すべての要素を少なくとも1回スキャンする必要があり、O（N）につながるからです。

于 2012-10-14T16:30:38.667 に答える