したがって、これは私の宿題の質問ではありませんが、アルゴリズムとデータ構造に関する Coursera コースの採点されていない宿題から取られています (これは現在完了しています)。
個別の数値の n x n グリッドが与えられます。数値がすべての隣接数値よりも小さい場合、その数値は局所的最小値です。(数字の隣とは、すぐ上、下、左、または右に 1 つです。ほとんどの数字には 4 つの隣りがあります。横の数字には 3 つ、四隅には 2 つがあります。) 分割統治アルゴリズムの設計を使用します。数値ペア間のO( n ) 比較のみで局所最小値を計算するパラダイム。(注: 入力にはn 2の数値があるため、それらすべてを調べる余裕はありません。ヒント: どのタイプの反復が望ましい上限を与えるかを考えてください。)
数字は順不同なので、O( n 2 ) 比較以外でどうすればうまくいくかわかりません。
Words Like Jared の回答は、それがどのようにうまくいかないかを調べることで適応させることができます。
その答えのアイデアは、良いものですが、「下り坂を転がる」ことです。これは、要素上にいる場合、それが局所的最小値であるかどうかを確認することを意味します。もしそうなら、あなたは終わりです。それ以外の場合は、その最近傍の最小値に進みます。最終的には、これは終了する必要があります。これは、すべてのステップがより小さな要素に対するものであり、有限配列内で永遠に続くことはできないためです。
このアプローチの問題は、「ローリング」があちこちで蛇行する可能性があることです。
20 100 12 11 10 100 2
19 100 13 100 9 100 3
18 100 14 100 8 100 4
17 16 15 100 7 6 5
左上から始めて「下り坂」にすると、配列内の要素の約半分にアクセスします。これは多すぎるので、少し制限する必要があります。
中央の列と中央の行を調べることから始めます。それらすべての中で最小の要素を見つけて、そこから始めます。
そこから 1 段「下り坂」に転がって、4 つの象限の 1 つに入ります。中央の列および/または行の隣接する要素が大きく、隣接する 2 つの象限のうちの 1 つだけが「下り坂」になる可能性があるため、象限の 1 つに入ります。
そこから「下り坂を転がり落ちた」としたらどうなるかを考えてみましょう。明らかに、最終的にはローカル ミニマムに到達します。（時間がかかりすぎるため、実際には行いません。）しかし、転がる過程で、その象限を離れることはありません...そうするためには、中央の列または中央の行のいずれかを通過する必要があるためです。 、そしてそれらの要素のどれも、あなたが始めた場所よりも小さくありません。したがって、その象限には極小値がどこかに含まれています。
したがって、線形時間では、極小値を含む必要がある象限を特定し、n を半分に削減しました。今すぐ再帰します。
このアルゴリズムには 2n + 2n/2 + 2n/4 + ... の時間がかかります。これは O(n) である 4n に等しいので、完了です。
興味深いことに、アルゴリズムが機能することを証明するという重要な部分を除いて、「下り坂を転がる」ことはほとんど使用しませんでした。
[アップデート]
Incassatorが指摘しているように、この答えは完全に正しいとは言えません。
最も簡単な解決策は、 「下り坂を転がる」前に、中央の行、中央の列、および境界の中から最小の要素を見つけることです。
これは実に簡単なことだと思います。
問題を 3 次元の問題に変換して、アルゴリズムが機能する理由を確認します。マトリックスをテーブルに置きます。各セルから伸びる柱があり、柱の高さがその値に正比例していると仮定します。いずれかの柱にボールを置きます。極小値になるまで、常に最も高度が低い隣接する柱にボールを落下させます。