0

私はJavaで次の問題を解決しようとしています(他のほとんどの言語でも実行できますが):

x軸上のdataPointを表す整数値との2つの配列が与えられますxsysそれらの長さは同じではない可能性がありますが、両方とも> 0であり、ソートする必要はありません。計算したいのは、ポイントの2つのデータセット間の最小距離測度です。つまり、たとえば、それぞれについて、セット内でx最も近いものを見つけて距離を計算します。例えば:yys(x-y)^2

xs = [1,5]
ys = [10,4,2]

(1-2)^ 2 +(5-4)^ 2 +(5-10)^2を返す必要があります

距離測度は重要ではありません。これは私が興味を持っているアルゴリズムです。ブルートフォースよりも優れたものを実現するために、両方の配列を並べ替えて、これらの配列の両方でインデックスを進めることを考えていました(xの各要素について、ysのすべての要素をスキャンして見つけます) min)これはO(len1 * len2)

これは私が取り組んでいる私自身の問題であり、宿題の質問ではありません。すべてのヒントをいただければ幸いです。

4

3 に答える 3

2

HighPerformanceMark(あなたの質問に対する最初のコメント)が正しいと仮定し、実際に大きい配列を取得し、各要素について小さい配列の最も近いものを見つけて、それらの距離にわたってf(dist)を合計します。

私はあなたのアプローチを提案します:

Sort both arrays 
indexSmall=0 

// sum up
for all elements e in bigArray {
  // increase index as long as we get "closer"
  while (dist(e,smallArray(indexSmall)) > dist(e,smallArray(indexSmall+1)) {
    indexSmall++
  }
  sum += f(dist(e,smallArray(indexSmall)));
}

これはO(max(len1,len2)*log(max(len1,len2)))ソート用です。残りは、より長いアレイ長に対して線形です。今は、、またはあなたが望むdist(x,y)もののようなものになります。abs(x-y)f(d)=d^2

于 2012-06-11T13:48:29.280 に答える
1

あなたのアプローチはかなり良く、O(n1*log(n1)+n2*log(n2))時間の複雑さがあります。

配列の長さが異なる場合、別のアプローチは次のとおりです。

  1. 短い配列を並べ替えます。
  2. 長い配列を最初から最後までトラバースし、バイナリ検索を使用して、並べ替えられた短い配列で最も近い項目を見つけます。

これにはO((n1+n2)*log(n1))時間計算量があります。ここn1で、は短い配列の長さです。

于 2012-06-11T13:37:09.830 に答える
1

あなたが提案したアイデアは私にはいいですね。O(n logn)時間でリストをソートできます。次に、もう一方のスライディングインデックスを使用して、長いリストに対して1回の反復を実行し、「ペア」を見つけることができます。長いリストを進めていくと、もう一方を後戻りする必要はありません。したがって、アルゴリズム全体はO(n logn + n)= O(n logn)になります。

于 2012-06-11T13:31:52.203 に答える