algorithm - 给定二部图的情况下使用斐波那契堆或二进制堆的基本算法的时间复杂度

我想进一步了解Primm的时间复杂度的细节。基本上，PRIM的时间复杂度为O(V^2)。当使用二进制堆或斐波那契堆时，时间复杂度被提升到O(E + V log(V))或 > >。我的问题如下。为什么有些代码使用基本的prim算法，甚至其他版本的prim都给出了更好的解决方案？使用基本prim算法是否有特殊的原因？。与高级prim版本相比，实现起来相当容易。否则，我假设没有特殊的理由使用基本prim算法。当给出二部图时，我可以将fibonacci或二进制堆prim版本应用于二部图而不是基本prim版本吗我分析的现有代码使用二分图中的基本Primm算法。我想做的是提高代码速度因此，我想使用二进制或fibonacci堆更改prim的数据结构，以减少执行时间对于二部图而不是普通图，是否可以使用高级prim版本？ 最佳答案 当在实际生活中实现算法时，渐近时间复杂度不是最重要的：实际效率和简单性也很重要。首先，虽然Fibonacci堆的Primm算法的理论复杂度优于二进制堆（O（E log v）vs O（e+v log v）），但是Fibonacci堆在实践中确实很慢，所以E值应该非常大，以注意差异。我还没有看到任何实际的例子。简单的二进制（或k元，k是4或8）非常非常快。其次，有稠密图（其中e~v^2）和稀疏图（其中e~v）。（当然也有中间类，但一般来说，任何实用图都可以看作稀疏或稠密的）。对于稠密图，无论是理论上还是实践上，标准Prim算法在O（V^2）运行时都是最好的也许这就是使用更简单版本的原因。或者性能在这一点上根本不重要，因为图表并没有那么大。关于第二个问题：我还没有听说过在二分图中找到mst的任何特定算法。当然，您可以应用任何版本的算法，但我怀疑存在任何特殊的技巧，为二分情况。对于稀疏图，考虑Kruskal算法它是O（E loge），但唯一重要的部分是排序，这在今天也是非常快的。关于algorithm - 给定二部图的情况下使用斐波那契堆或二进制堆的基本算法的时间复杂度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47450640/