こんにちは、このフォーラムでいくつかの調査を行いましたが、私の問題に対する適切な回答が実際には見つかりませんでした。可能な限り最速のアルゴリズムで金融問題を解決する必要があります。ポイントの p セットが与えられた場合、各セットには n ポイントがあり、すべてのポイント セット間の最も近いポイントをすべて計算するアルゴリズムを見つける必要があります。最も近いペアアルゴまたは最も近いネイバーで実行できると思いますが、o（n ^ 2）未満の操作でどのように作成できるかわかりません。
2 に答える
0
そのため、ルックアップを高速化するために使用できるアクセラレーション構造がいくつかあります。セットごとに Kd ツリーを作成できます。これは、各ルックアップに O(log(n)) がかかることを意味するため、すべてのルックアップの合計は O(n log(n)) になります。
kd ツリーの作成には、それ自体で O(n log(n)) が必要です。それらを一緒に追加しても、O(n log(n)) になります。
ただし、ほとんどの現実のケースでは、考慮すべきは O だけではありません。スカラー係数も非常に重要です。Kd ツリーの実装は非常に簡単です。データの形状 (オーバーラップが多いかどうか) によっては、別のアクセラレーション構造を使用して、さらに速度を上げることができる場合があります。
于 2013-11-12T09:56:57.367 に答える