1. 序章


このチュートリアルでは、配列内の絶対差が最小の2つの数値を見つける方法を示します。


2. 最小限の違い








数値配列があり、最も近い2つの数値を見つけたいと考えています。


たとえば、の場合、最小の絶対差はとの間であるため、アルゴリズムはペアを出力する必要があります。


3. 解決


降順ではない順序でソートしたとしましょう：。 次に、それぞれに最も近い番号は、その直前または直後です。 つまり、配列が並べ替えられている場合は、連続する要素間の違いのみをチェックする必要があります（順序は関係ありません）。


したがって、それぞれの並べ替えと計算を繰り返すことで、最小の違いを見つけることができます。 たとえば、並べ替えると、が得られます。 連続する要素間の絶対差は、それぞれです。 したがって、答えは2番目のペアです。


3.1. 擬似コード


擬似コードは次のとおりです。




まず、配列を並べ替えます。 次に、最初のペアを現在の最も近いペアとして宣言し、残りをループします。 絶対差が小さい2つの連続した数値が見つかった場合は、現在の最も近いペアを更新します。


3.2. 複雑


このアプローチの時間計算量はどれくらいですか？ ソートアルゴリズムに依存しますソートされた配列の最小の差の検索は、最悪の場合と平均的な場合であるためです。 マージソートでは、最悪の場合、ソート部分に時間がかかるため、アルゴリズム全体の複雑さはです。


最悪の場合の時間計算量がであるQuicksortを使用した場合、最悪の場合のアプローチも2次式になります。 ただし、クイックソートは平均的なケースでは対数線形であり、マージソートよりも乗法係数が小さくなります。 そのため、マージソートの代わりにクイックソートと線形検索を組み合わせると、実際にはより速く機能する可能性がありますが、後者の方が漸近的に有利です。


さて、問題は次のとおりです。


4. 一次元でのラビンのアルゴリズム


そして答えは、少なくとも確率的な時間計算量に関しては、私たちができるということです。 1976年、 マイケルO。 ラビンで最も近いペアを見つけるためのランダム化アルゴリズムを定式化し、それが高い確率で線形時間計算量を達成したことを証明しました。 の場合、最も近いペアの問題は私たちの問題になります。


4.1. アイデア


主なアイデアは次のとおりです。 まず、（）から数値のペアをサンプリングし、ペア間の最小の差を計算します。 と表記しましょう。 その後、すべての数値を長さの連続するセグメントに並べ替えます。


次に、最も近い2つの番号は、同じセグメントまたは2つの隣接する番号のいずれかにあります。


したがって、セグメントを反復処理し、計算された最小の差を追跡しながら、各セグメントと2つの連続するペアごとに最も近いペアを見つけます。 結局、それはの実際の最小差に対応します。


4.2. 擬似コード


擬似コードは次のとおりです。




最初に、ペアをサンプリングして最も近いペアを決定します。これら2つの数値の絶対差とします。 次に、配列をワイドセグメントに分割します（それらがあると仮定します）。 商を切り捨てることで、該当するセグメントを特定できます。 したがって、同じセグメントに属する番号を、の同じエントリに保持します。この辞書の整数キーは、幅の広いセグメントを識別し、値は配列（リストまたはツリー）です。 ）対応する要素の。


その後、ソートされた順序でキーをループします。 配列全体で最も近い2つの数値は、同じセグメント内か、2つの連続した数値のいずれかです。したがって、ループオーバーして、現在の最も近いペアをそれぞれの最も近いペアと比較します。 存在する場合は、一方がに属し、もう一方がに属するように、2つの数値を比較します。


4.3. 時間計算量


このアルゴリズムは、2次ブルートフォースアプローチを使用して個々のセグメントで最も近いペアを見つける場合でも、高い確率で線形の予想時間計算量を持ちます。


5. 結論


この記事では、配列内で最も近い2つの数値を見つける方法を示しました。 2つのアルゴリズムを提示しました。1つは並べ替えに基づくもので、もう1つはランダム化されたものです。 前者はマージソートを使用する場合、最悪の場合対数線形ですが、後者は高い確率で線形の期待時間を達成します。