8

0<=i<=n-1 の配列 a[i] があるとします。複雑さ O(log n) のアルゴリズムを使用して、1<=i<=n-2、a[i]<=a[i+1]、a[i]<=a[i -1]? つまり、対数時間で極小値を見つけることができますか?

注：私は（何度も変更された）質問を編集して、合理的に回答できるものにしました。このバージョンはより単純でありながら一般性を失っていないため、以前のバージョンにあった奇妙な終了条件を削除しました。

4

7 に答える 7

6

まず、局所最小値がどのように定義されるかを考慮する必要があります。

a[i] < a[i-1] and a[i] < a[i+1]

この条件から、配列を X/Y グラフ (X = インデックス、Y = 値) にプロットすると、極小値が谷にあることがわかります。したがって、極小値が存在することを確認するには、勾配符号の変化 (減少から増加へ) が存在することを保証する必要があります。

範囲の終点勾配の動作がわかっている場合は、範囲内に極小値があるかどうかがわかります。さらに、配列には a[0] から a[1] に勾配符号が減少し、a[n-1] から a[n] に勾配符号が増加する動作が必要です。そうでない場合、問題は簡単です。検討：

a = [1,2,3,4,5] (increasing, increasing) a[0] is an LM
a = [5,4,3,2,1] (decreasing, decreasing) a[n] is an LM
a = [1,2,2,2,1] (increasing, decreasing) a[0] and a[n] are LMs

これは、メソッドを完成させるのに十分なインスピレーションになると思います。

このメソッドの拡張は、すべて 1 の配列などの一意の値にのみ適していることに注意してください。エッジ ケースの検出を行わない限り、O(log n) の実行時間はありません。

于 2012-08-03T21:53:49.633 に答える
3

配列に他の制約がない限り、最悪の場合、配列内のすべての要素をチェックする必要があるため、(少なくとも) 線形時間の前処理なしで O(log n) の極小値を見つけることはできません。このステートメントを正式に証明することは難しくありません。アイデアは、各スキャン方法に対して、この方法が構築された配列で線形時間で機能するような配列を構築することです。

たとえばn、最初から最後までサイズの配列で単純なスキャンを行っている場合を想像してください。最小値がn-1- 番目の位置にある場合、n-1反復後にのみ検出されます。O(n)

http://www.careercup.com/question?id=8223978

于 2012-08-03T21:41:05.543 に答える
1

O(log n) のバイナリ検索アプローチと同様に解決されますが、配列に局所的な最小値と個別の数値が 1 つある場合のみです。配列は次のようにする必要があります。

8 5 4 3 [1] 2 6 9

1 つはここでのローカル ミニマムです。

境界を確認します。a[0] < a[1] の場合、a[1] は極小値です。a[n-1] > a[n] の場合、a[n] は極小値です。これらの条件のいずれにも当てはまらない場合 - 分割を開始します。

a[n/2] > a[n/2 + 1] の場合は a[n/2] をチェックし、配列の右側の局所的最小値、それ以外の場合は左側の局所的最小値をチェックします。その後、問題を再帰的に解決します。

于 2012-08-03T21:53:53.453 に答える
0

このソリューションの動作を反証することはできないので、誰かができれば幸いです。

1 から n までのインデックスが付けられた配列 'a' を考えてみましょう。

low = 1
high = n
mid = (low + high)/2

一般性をあまり失うことなく、配列の値が異なると仮定します。したがって、ミッドでは、a[mid - 1]、a[mid]、a[mid + 1] は次のようになります。

Case 1:

/\


Case 2:

\/

Case 3:

 / 
/

Case 4:

 \
  \

Case 5(boundary):
/

Case 6(boundary):
\

&m = 中

各ケースは、次の if 条件を使用して確認できます。

1: a[m] > a[m-1] && a[m] > a[m+1]
2: a[m] < a[m-1] && a[m] < a[m+1]
3: a[m] > a[m-1] && a[m] < a[m+1]
4: a[m] < a[m-1] && a[m] > a[m+1]

また、境界ケースの説明も無視します。

2 番目のケースは、a[m] が極小である望ましいケースです。

3番目のケースの場合:

極小値は常に左側にあるため、h = m - 1 に設定して続行します。

4番目のケース：

常に右側に極小値があるため、l = m + 1 で続行します。

最初のケースでは、どちらの方向にも進むことができます。検討しているセグメントを縮小するのは、縮小されたセグメントに極小値があることが確実な場合のみであるため、これが機能すると考えています。したがって、検索するセグメントは常にいくつかの極小値。

注: これは、すべての極小値ではなく、単一の極小値を見つける場合にのみ機能します。後者の場合、少なくとも 1 回は配列全体を表示する必要があるため、O(n) が必要になります。

于 2014-02-15T06:39:06.587 に答える
-1

編集:これは、ローカル最小値が「<」ではなく「<=」で定義されている場合にのみ機能します。ただし、「<」では解決しません。したがって、OPの（解決できない）質問を解決しないことに注意して、これをここに保持します。

次の分割統治法は、少なくとも 1 つの局所的最小値が存在する場合、O(log n) で局所的最小値を見つける必要があります。

  1. 最初、最後、および中間の要素を考えてみましょう (それらを A、B、C と呼びましょう)。
  2. A が 3 つのうち最小の場合は、配列の前半に進みます。
  3. それ以外の場合、C が 3 つの中で最小の場合は、配列の後半に進みます。
  4. それ以外の場合 (つまり、B が 3 つの中で最小の場合)、前半の中央要素 (D) が B よりも小さいかどうかを確認し、その場合は左半分を使用します。
  5. それ以外の場合は、右半分 (E) の中間要素が B よりも低いかどうかを確認し、その場合は後半を使用します。
  6. それ以外の場合は、D から E までの要素を続行します (B は中央にあります)。

2. - 6. の各ケースで、左と右に (必ずしも直接ではありませんが) より高い要素を持つ要素、または境界にある要素を続行します。考慮する要素の数が半分になるたびに、O(log n) になります。最終的には 3 つ以下の要素のみを考慮し、これらの最小数は局所的最小値です。

于 2012-08-03T22:00:19.567 に答える
-2

これは宿題の質問だと思いますので、適切に答えています。ローカル ミニマムを検索する場合は、「ローカル」とは何かの参照が必要なため、開始位置を指定する必要があります。左の要素がその要素より小さい場合は、その要素に移動して再試行します。それ以外の場合、右側の要素が現在よりも小さい場合は、右に移動して再試行します。それ以外の場合、現在の要素はローカル最小値です。

編集:質問を読んだ後、O(log n)時間の要件が追加されました。この要件を満たす解決策を考えます。

別の編集:問題を半分に分割する方法がないため、ソートされていない配列の O(log n) の時間要件でこれが可能であるとは思いません。一方、ソートされた配列には簡単な O(1) ソリューションがあります:)

于 2012-08-03T21:39:15.983 に答える