2

円nに配置された整数は、1つのピークを見つけることができる効率的なアルゴリズムを示しています。ピークとは、その隣にある2つの数値以上の数値です。

1つの方法は、すべての整数を調べて、それぞれをチェックして、それがピークであるかどうかを確認することです。それはO(n)時間を生み出します。しかし、より効率的にするために分割統治する方法があるはずです。

4

3 に答える 3

3

編集

さて、キース・ランドールは私が間違っていることを証明しました。:)

Pythonで実装されたKeithのソリューションは次のとおりです。

def findPeak(aBase):
    N = len(aBase)
    def a(i): return aBase[i % N]

    i = 0
    j = N / 3
    k = (2 * N) / 3
    if a(j) >= a(i) and a(j) >= a(k)
        lo, candidate, hi = i, j, k
    elif a(k) >= a(j) and a(k) >= a(i):
        lo, candidate, hi = j, k, i + N
    else:
        lo, candidate, hi = k, i + N, j + N


    # Loop invariants:
    # a(lo) <= a(candidate)
    # a(hi) <= a(candidate)

    while lo < candidate - 1 or candidate < hi - 1:
        checkRight = True
        if lo < candidate - 1:
            mid = (lo + candidate) / 2
            if a(mid) >= a(candidate):
                hi = candidate
                candidate = mid
                checkRight = False
            else:
                lo = mid
        if checkRight and candidate < hi - 1:
            mid = (candidate + hi) / 2
            if a(mid) >= a(candidate):
                lo = candidate
                candidate = mid
            else:
                hi = mid

    return candidate % N
于 2012-10-12T21:05:07.853 に答える
2

これが再帰的O(log n)アルゴリズムです。

数値の配列があり、そのセグメントの中央の数値が端点より小さくないことがわかっているとします。

A[i] <= A[m] >= A[j]

for i、jは配列にインデックスを付け、そしてm=(i+j)/2。エンドポイントとミッドポイントの中間の要素、つまりインデックスx=(3*i+j)/4との要素を調べますy=(i+3*j)/4。の場合A[x]>=A[m]、間隔で繰り返します[i,m]。の場合A[y]>=A[m]、間隔で繰り返します[m,j]。それ以外の場合は、間隔で繰り返します[x,y]。

いずれの場合も、上記の間隔で不変条件を維持します。最終的に、サイズ2の間隔に到達します。これは、ピークが見つかったことを意味します（これはになりますA[m]）。

円を配列に変換するには、3つの等距離のサンプルを取得し、最大（または最大のものに結び付けられたもの）が間隔の中央にあり、他の2つの点が端点になるように向きを変えます。実行時間はO(log n)、各間隔が前の間隔の半分のサイズであるためです。

インデックスを計算するときの丸め方の問題については詳しく説明しましたが、うまくいくと思います。

于 2012-10-12T21:56:28.997 に答える
0

「円を描くように配置されている」とは、循環リンクリストのようなものですか？データセットを説明する方法から、これらの整数は完全に順序付けられていないように聞こえます。N個の整数を調べて、他の整数について何らかの結論を出す方法はありません。その場合、力ずくの解決策が唯一の可能な解決策です。

編集：

最悪の場合の時間を気にしないのであれば、もう少し効率的な方法があります。素朴なアプローチは、N i、N i-1、およびN i + 1を調べて、Niがピークであるかどうかを確認してから繰り返すことですが、もう少しうまくいくことができます。

While not done
    If N[i] < N[i+1]
        i++
    Else
        If N[i]>N[i-1]
            Done
        Else
            i+=2

（まあ、それは完全ではありません。N[i] = N [i + 1]の場合に対処する必要があるからです。しかし、非常によく似ています。）

これにより、少なくともNiとNi + 1を比較し、1をiに加算してから、NiとNi-1を重複して比較することを防ぐことができます。ただし、これは明らかにわずかな利益です。あなたはまだ数字を行進していますが、それを回避する方法はありません。盲目的にジャンプすることは役に立たず、実際の仕事をするのと同じくらい長くかかることなしに先を見据える方法はありません。

于 2012-10-12T21:04:22.053 に答える