1

f(1) > f(2) > f(3) > f(4) ....... > f(k -1) > f(k) < f(k+1) < f(k+2) < ....... < f(n) f( k) は、シーケンスと O(lgn) 時間の最小値です。この問題を解決するために、次のバイナリ検索ベースのアルゴリズムを考案しました。アルゴリズムが正しいかどうか教えてください。

二分探索が再帰する場所を決定するために使用されるプロパティ -:

FindMin(F , lo , hi)

if(lo == hi) return F[lo];

int mid = lo + (hi-lo)/2;

// recurse to the left
if(F[mid] < F[mid+1]) return FindMin(F , lo , mid);
// recurse to the right
if(F[mid] < F[mid - 1]) return FindMin(F , mid , hi);

return F[mid];

誰かが私のアルゴリズムが正しいかどうかを確認できますか?

4

3 に答える 3

2

現在のアルゴリズムは正しくありませんが、それにかなり近づいています。ここで、アルゴリズムがどこでうまくいかないかを示します。

配列を考えてみましょう[3,2,1,2]。

最初に電話するとします。FindMin(F, 0, 3)

FindMin(F, 0, 3)
--ミッド = 1
-- F[1] False をチェック
-- F[1] True をチェックし、FindMin(F, 1, 3) を呼び出します。
----ミッド = 2
----F[2] True をチェックし、FindMin(F, 1, 2) を呼び出します
------ミッド = 1
------チェック F[1] False
------F[1] True を確認し、FindMin(F, 1, 2) を呼び出します
--------ミッド = 1
--------チェック F[1] False
--------F[1] が真であることを確認し、FindMin(F, 1, 2) を呼び出します
...これは、メモリがなくなるまで永遠に続きます

少し変更して正しくすることができます：

FindMin(F, lo, hi){
    if(lo==hi) return F[lo];
    int mid = lo + (hi-lo)/2 // Actually you can change this into (lo+hi)/2
    if(F[mid] > F[mid+1]) return FindMin(F, mid+1, hi) // Change the comparison and recursive call!
    if(F[mid] > F[mid-1]) return FindMin(F, lo, mid-1) // Change the comparison and recursive call!
    // If we reach here, that means F[mid-1] > F[mid] < F[mid+1]
    return F[mid]
}

@Joniが言ったように、境界ケースを処理する必要があります。チェックするだけでF[mid+1]うまくいきます。この次のコードは、範囲外のエラーが発生せず、正しいことを保証します。

FindMin(F, lo, hi){
    if(lo==hi) return F[lo];                           // Line 1
    int mid = (lo+hi)/2                                // Line 2
    if(F[mid] > F[mid+1]) return FindMin(F, mid+1, hi) // Line 3
    else return FindMin(F, lo, mid)                    // Line 4
}

hi配列の最後のインデックスとして関数を呼び出します

ライン 1 は基本ケースです。

行 2 は、中間インデックスを計算します。mid < hiここで、は 1 行目で既に説明されているので、 をmid == hi意味することに注意してください。だから安心してチェックできるlo == himidF[mid+1]

行 3 は、ある数値よりも大きく、さらに大きくなる可能性があるため、 である場合、 は答えではないF[mid] > F[mid+1]かどうかをチェックします。したがって、答えは にある必要があります。だから電話してください。であるため、範囲は よりも小さいことに注意してください。F[mid]F[lo..mid-1]F[mid+1..hi]FindMin(F, mid+1, hi)mid+1 > lomid+1..hilo..hi

4 行目: ここまで来ると、つまりF[mid] < F[mid+1]. したがって、答えは のどこにでもあり得ますF[lo..mid]。だから電話してFindMin(F, lo, mid)ください。mid < hi以降、FindMin(F, lo, mid)とは異なることに注意してくださいFindMin(F, lo, hi)。より具体的には、3 行目の場合のように範囲が減少します。

ライン 3 とライン 4 を組み合わせると、 への各呼び出しFindMinは減少する範囲で行われるため、アルゴリズムはライン 1 でしばらくすると停止するはずです。

于 2013-09-27T06:31:40.083 に答える
1

仮定しmid = kます。次に、最初の条件が真で、 を繰り返しますlo, mid。そのセクションでは、要素は降順であり、 で繰り返されるまで 2 番目の条件に従いますk-1, k。しかしmid = k-1 + (k-(k-1))/2 = k-1、整数除算によって。これは正しくないです。2 番目の条件 - 無限ループ on を満たし続けますk-1, k。

比較記号が逆になっているようです。

于 2013-09-27T00:14:20.250 に答える
1

アルゴリズムの基本原則は正しいです。最小値が右にあるか左にあるかを判断するには、中間点を使用します。

しかし、それは完全に正しいわけではありません。midが最小要素であるF[mid] < F[mid+1]場合に何が起こるかを考えてみてくださいF[mid] < F[mid-1]。最小値を返すことはできません。無限再帰に入ります。ただし、簡単な修正があります。

覚えておく必要があるもう 1 つのことは、最小値がシーケンスの最初または最後の要素である場合に何が起こるかということです。計算できないF[mid-1]かF[mid+1]、インデックスが範囲外になるためです。

于 2013-09-27T00:17:56.063 に答える