algorithm - 配列内のピークを見つける際に適用される分割統治アルゴリズム。

Question

配列 a: a ₁ , a ₂ , … a _k , … a _nの場合、 1 < k および k < n のときにa _k-1 ≤ a _k ≥ a _k+1である場合に限り、a _{kはピークです。}a ₁ ≥ a ₂の場合、a _{1はピークであり、a n-1} ≤ a _nの場合、 a _nはピークです。目標は、配列から 1 つのピークを見つけることです。

分割統治アルゴリズムは次のように与えられます。

find_peak(a,low,high):
    mid = (low+high)/2
    if a[mid-1] <= a[mid] >= a[mid+1] return mid // this is a peak;
    if a[mid] < a[mid-1] 
        return find_peak(a,low,mid-1) // a peak must exist in A[low..mid-1]
    if a[mid] < a[mid+1]
        return find_peak(a,mid+1,high) // a peak must exist in A[mid+1..high]

このアルゴリズムが正しいのはなぜですか? ピークが存在するアレイの半分を失うことで問題が発生する可能性があると思います。

Answer 1

アルゴリズムは正しいですが、証明するには少し計算が必要です。最初のケースは些細な→ピークです。2 番目のケースは「ハーフ ピーク」です。つまり、下り勾配がありますが、上り勾配はありません。

ここには 2 つの可能性があります。

• 関数は a _mid → a ₁ ≥ a ₂がピークになるまで単調減少します。
• _{関数は a mid}まで単調減少しない→ a _k ≥ a _k-1である a ≥ k ≥ mid が存在する。このステートメントが真となる最大の k を選択しましょう → a _k+1 < a _k ≥ a _k-1 → そしてそれがピークです。

同様の議論は、反対の「ハーフピーク」を持つ 3 番目のケースにも適用できます。