0

たとえば、 D 次元のユークリッド空間では、N 個の格子点が与えられます ( 例: 最高の 6D 空間が可能です )。次に、すべてのペアのユークリッド距離を見つけなければなりません。現在、通常は n^2 ループを使用しますが、N = 5000 の場合、この O(n^2) は遅すぎます。距離を見つける効率的な方法はありますか?

4

2 に答える 2

1

N*(N-1)/2 のペアがあるため、O(N^2) が最適な時間です。

于 2013-04-12T11:24:25.733 に答える
0

@MBo はO(N^2)最高のビッグオー時間であるという点で正しいですが、ポイントが実際に特別な種類の格子、つまり長方形格子上にある場合は、対称性を利用して前因子を下げることができます。一般に、D 次元の正方格子がm各方向に最大で 1 単位外側に伸びると仮定できます。これはN=2*d*mポイントを与えます。他の次元は同じになるため、このラティスの上部象限のみを計算する必要があります。たとえば、2D で次の点を考えてみましょう。

(3,4)   -> 5
(-3,4)  -> 5 
(3,-4)  -> 5 
(-3,-4) -> 5

一般に、計算を係数ポイントで減らすことができます(2^d-1)。これは、より高い次元では重要です。6 次元では、これは の定数係数です63。

于 2013-04-12T14:47:55.437 に答える