我正在尝试实现一种分而治之的算法，以使用 JavaScript 在随机生成的一组点中找到最近的一对点。该算法应该在 O(n log n) 时间内运行，但它的运行时间比简单的蛮力算法要长得多，后者应该是 O(n^2)。
我创建了两个 jsfiddles，为 16000 个点的数组计时算法：
我的假设是分而治之非常慢，因为 JavaScript 数组实际上是哈希表。是否可以显着加快 JavaScript 中的算法速度？如果是这样，这样做的最佳方法是什么？
问问题
1949 次
1 回答
2
乍一看，您的合并函数分配了太多的内存（大约为 O(n^2)）。我在这里做了一个 hacky 方法来测量这个。基本思路是我只是在全局范围内有一个计数器，每次调用merge生成的数组的大小相加。希望这些信息足以让您修复它，如果您遇到更多问题，我很乐意提供一些额外的指示。
此外，只需使用数字，就很容易排除它是哈希表问题* - 哈希表减慢的算法不会表现出比 O(n log n) 更快的增长率，它只会开始缓慢并增长沿着同样的路线。但是，如果您尝试一系列值，应该会发现它的增长速度比这更快，这表明存在不同的问题。
* javascript 数组的内部实现比它们只是对象要复杂一些，但就这一点而言，我试图让它并不重要
于 2012-10-17T04:39:54.170 回答