アルゴリズムについて話しましょう。初心者は、それらを困難で、複雑で、理解できないものとして認識することがよくあります。これは部分的には真実ですが、アルゴリズムが基本です。そして、あなたが自分の専門分野の基本をよく知っているほど、あなたはそれに優れている可能性が高くなります。
今日は、1つの美しいアルゴリズムの問題を見ていきます。最初からアルゴリズムを使用することから人々を怖がらせることはない ので、分析では、セグメントのツリーの広がり、ナップザック問題のさまざまな最適化、または単純化のための確率的テストはありません。ユーザーフレンドリーなアルゴ。
ここに課題があります：隣人の間の最大の違いを見つけてください。
N個の整数の配列が与えられます。順序付けはされておらず、番号を繰り返すことができます。それをソートし、連続する要素の各ペア間の差を計算したとします。そのような最大の違いを見つけて、それを最適な方法で行う必要があります。
複雑ですか？ [続きを読む]をクリックする前にこれを試してから、解決策を確認してください。
じゃあ行こう。隣人間の最大差。
例を考えてみ
ましょう。N= 11個の要素の配列が与えられたとします。
最初に、単純な問題を解決させ、それはしばしば役立ちます。問題が私たちに要求することを正確に行うことができます-番号を並べ替えて、隣接する要素間の違いを見つけます。ソリューションの複雑さは、使用する並べ替えによって異なります。 qsortまたは mergesortを使用する場合
、時間の複雑さは 。数値が整数のセットにかなり密に分布していることがわかっている場合は、カウントソートを使用できます。次に、 、ここでUは最大要素と最小要素の差です。このケースは比較的まれですが、この可能性を覚えておく価値があります。
ソート後、配列を取得します。
差異の配列アウトレッツライト： 私たちが得る最大の差は6であることを 今度は、考えてみましょう、それはより速く、問題を解決することができますか？隣接する要素のペアを反復処理する場合、わずかな違いで多くのペアを検討します。そのようなペアは決して最大の違いを与えることができないかもしれません。確かに、ソートされた配列には
対の隣接する番号、最大値と最小値の差を 。次に、最大の違いは少なくとも 。この見積もりは、ディリクレの原則によって当てはまります。
ハトがケージに配置され、ハトの数がセルの数よりも多い場合、ケージの少なくとも1つに複数のハトが含まれます。
9個の細胞は10羽のハトが含まれている、ディリクレの原理に従って、少なくとも1つのセルが複数の鳩（含まれているウィキペディア）
してみましょうを 、... 、 -ソートされた配列のi番目の要素。次に 。 すべてのD [i]の最大値が小さいと仮定すると
、次いで全体和 厳密に小さいU、矛盾よりあろう。
素晴らしい、最大差の下限があります！次に、互いに近すぎる要素を何らかの方法でローカライズしてみましょう。セグメントを最小要素から最大要素まで、長さの半分の間隔に分割します。 。各要素はちょうど1つの半間隔に分類されます。すべての要素を重複しないグループに分割します。これらはバッチとも呼ばれます。
要素xがどの要素に該当するかを判断するのは非常に簡単です-1+ int（（x --a_min）/ L）（1から数えます）を計算する必要があります。ここで、a_minは配列Aの最小要素であり、1回のパスで見つけることができます。元の配列。唯一の例外は最大要素です-そのような値を持つ要素を別のバッチで作成することをお勧めします。
この図は、上記の例の分布を示しています。わかりやすくするために、これを手で行いましょう。
バッチ配布は線形時間で実行され、 追加メモリ。1つのバッチのアイテムでは、2つのアイテムの間に最大の差を与えることはできないことに注意してください。このようにサイズを特別に選択しました。
2つの隣接する要素はどこにありますか？もちろん、隣接する空でないバッチでは！たとえば、この図では、3番目と6番目のバッチの要素は、それらの間のバッチが空であるため、並べ替えられた配列の行に配置できます。2つの要素のみが隣接することは明らかです。3番目のバッチからの最大値と6番目からの最小値です。同様に、差が最大のペアの候補は、最初のバッチの最大要素と3番目のバッチの最小要素になります。
最大の違いをもたらす可能性のある要素のすべてのペアを書き留めましょう。 min（i）-i番目のグループの最小要素、max（i）-最大要素として表します。
最大（1）= -1分（3）= 3
最大（3）= 4分（6）= 10
最大（6）= 10分（8）= 15
最大（8）= 15分（10）=
最大20 （10）= 21分（11）= 22
検討する価値のあるペアを特定しました。実際には、すべてのバッチを1回通過し、最後の空でないバッチとその最大値を維持する必要があります。次の空でないバッチに出くわしたとき、その中の最小値を見つけて、答えを更新しようとします。
私たちは喜ぶでしょう-私たちは時間内に問題を解決しました 。
実際、私たちはかなりよく知られたアイデアを使用し、実際にはポケットソートの最初のステップを実行しました。元々はバケットソートと呼ばれていました 。
アイテムはバスケットに配置され、次に各バスケット内のアイテムが並べ替えられます
。最悪の場合、 ですが、十分な数のバッチと要素の均一な分布がある場合の平均実行時間は 。
「でも待ってください。でも、 、なぜあなたはそれを考慮しなかったのですか？」-注意深い読者は尋ねます。このケースは縮退しているため、考慮していませんが、完全を期すために今すぐ実行しましょう。
最小値と最大値の差がゼロの場合、最大差もゼロになります。実際、それだけです。