c# - 一連の xy 座標における最短距離

Question

問題に対して 2 つの異なるアルゴリズムを比較する課題があります。問題は次のとおりです。

次のような一連の xy 座標があるとします。

A(2,3)、B(5,6)、C(7,8)、D(6,2)、E(5,5)など。

そして、それらの間の距離が最も短い2つの座標を見つけたいです。解決策の1つは、ブルートフォース（1つずつ一致させる）を使用することですが、「分割統治」方法を使用する別の解決策があります..

「分割統治法」について教えてください。

Answer 1

再帰的な分割統治法は次のように機能します。

1) ポイントを x 座標に従って並べ替えます。
2) 垂直線 x=xmid によって点のセットを 2 つの等しいサイズのサブセットに分割します。

3) 左部分集合と右部分集合で問題を再帰的に解きます。これ
により、左側と右側の最小距離 dLmin と dRmin がそれぞれ得られます。

4) 1 つの点が分割垂直線の左側にあり、2 番目の点が右側にある点のペアの間で最小距離 dLRmin を見つけます。

5) 最終的な答えは、dLmin、dRmin、および dLRmin の最小値です。（ソース）

の複雑さがありO(n log n)ます。また、疑似コードの実装がここにあり、メソッドの視覚的な説明がここにあります。

Answer 2

「分割」と「マージ」の部分の意味を考えてください。明らかに「分割」とは、問題を2つの小さな別々の問題に分割することを意味します。どのように？次に、2つの小さな問題を解決したとすると、どのようにそれらをマージしますか？両方の方法の時間計算量はどれくらいですか？さらに明確にする必要がある場合は、コメントを残してください。