algorithm - 度量空间中的高效最小生成树

Question

我在某个度量空间(例如配备 Jaccard Distance )中有大量点(n > 10000)。我想将它们与最小生成树连接起来，使用度量作为边上的权重。

• 是否有运行时间小于 O(n²) 的算法？
• 如果不是，是否有一种算法的平均运行时间少于 O(n²)(可能使用随机化)？
• 如果不是，是否有运行时间少于 O(n²) 并给出最小生成树的良好近似的算法？
• 如果不是，是否存在这样的算法不存在的原因？

提前致谢!

编辑以下海报: 寻找最小生成树的经典算法在这里不起作用。它们的运行时间有一个 E 因子，但在我的例子中 E = n² 因为我实际上考虑了完整的图。我也没有足够的内存来存储所有 >49995000 条可能的边。

Answer 1

显然，根据这个:Estimating the weight of metric minimum spanning trees in sublinear time没有确定性的 o(n^2)(注意:smallOh，我想这可能是你所说的小于 O(n^2) 的意思)算法。该论文还给出了度量最小权生成树的次线性随机化算法。

另请看这篇论文:An optimal minimum spanning tree algorithm这给出了一个最优算法。该论文还声称，最优算法的复杂度目前还不得而知!

第一篇论文中的引用文献应该会有帮助，那篇论文可能与您的问题最相关。

希望对您有所帮助。