javascript - JavaScript 中的最近对算法

Question

我正在尝试实现分而治之算法，以使用 JavaScript 在随机生成的点集中找到最近的一对点。该算法应该在 O(n log n) 时间内运行，但它比简单的蛮力算法运行时间要长得多，后者应该是 O(n^2)。

我创建了两个 jsfiddle，为 16000 个点的数组计算算法时间:

• Divide and Conquer
• Brute Force

我的假设是，分而治之之所以如此缓慢，是因为 JavaScript 数组实际上是哈希表。是否有可能显着加快 JavaScript 中的算法？如果是这样，执行此操作的最佳方法是什么？

Answer 1

一眼看去，您的合并函数分配了过多的内存(大致顺序为 O(n^2))。我做了一个 hacky 的方法来测量这个 here .基本思想是我在全局范围内只有一个计数器，并在每次调用时添加由 merge 生成的数组的大小。希望这些信息足以让您修复它，如果您遇到更多问题，我很乐意提供一些额外的建议。

另外，仅仅通过玩弄数字就很容易排除它是哈希表问题* - 被哈希表减慢的算法不会表现出比 O(n log n) 更快的增长率，它只会开始缓慢并沿着相同的路线增长。但是，如果您尝试一系列值，很明显它的增长速度比这快，这表明存在不同的问题。

*javascript 数组的内部实现比它们只是对象要复杂一点，但就我试图说明的观点而言，这并不重要