c - 金融中的计算几何算法？

Question

嗨，我在这个论坛上做了一些研究，并没有真正找到我的问题的正确答案。我需要用最快的算法解决财务问题。给定 p 组点，每组有 n 个点，我需要找到算法来计算每组点之间的所有最近点。我认为它可以用最近的对算法或最近的邻居来完成，但我不知道如何在少于 o(n^2) 的操作中做到这一点。

Answer 1

因此，您可以使用一些加速结构来获得更快的查找速度。您可以为每个集合创建一个 Kd 树。这意味着每次查找将花费 O(log(n))，因此所有查找的总数将为 O(n log(n))。

kd 树的创建本身需要 O(n log(n))。将它们加在一起仍然得到 O(n log(n))。

然而，在大多数实际情况下，O 并不是唯一需要考虑的因素——标量因素也非常重要。Kd 树的实现非常简单。根据数据的形状（是否有很多重叠），您可能能够使用不同的加速结构找到更高的速度。

Answer 2

如果这是一个代码问题，至少给出一些代码。如果它是一个数学问题，那么就有一个专为数学而设的划分。