Prim算法时间复杂度

Question

我一直在寻找在维基百科条目的Prim算法和我注意到，它的时间与邻接矩阵复杂度为O（V ^ 2），并与堆和邻接表它的时间复杂度是O（E LG（V））其中，E是边缘的数量，V是图中顶点的数目。

由于Prim算法是更致密的曲线图使用，E可以接近V ^ 2，但是当它，与堆的时间复杂度变为Ô（V ^ 2 LG（V）），这是为O（V ^ 2更大）。显然，堆将提高性能在刚刚搜索阵，但时间复杂度，否则说。

如何算法实际上的改善减缓？

Answer 1

即使堆从通过阵列搜索可以节省，它减慢了该算法的“更新”部分：阵列更新O（1），而堆更新为O（log（N））

在本质上，你在另一个交易速度在该算法对速度的一个部分。

不管你要搜索N次什么。 然而，在密集的图形，你需要更新大量（〜Ⅴ类^ 2），而在稀疏图，你不知道。

了我的头顶部另一个例子是搜索数组中的元素。 如果你只是做了一次，线性搜索是最好的 - 但是如果你做大量的查询，最好对它进行排序，并使用二进制搜索每次

Answer 2

从算法导论（卡门）

<强>时间=Θ（V）·T（EXTRACT-MIN）+Θ（E）·T（DECREASE-KEY）

                   T(EXTRACT-MIN)   T(DECREASE-KEY)   Total

1. array            O(V)             O(1)              O(V^2)
2. binary heap      O(lgV)           O(lgV)            O(E lgV)
3. Fibonacci heap   O(lgV)           O(1)              O(E + VlgV)

使用不同的数据结构引起不同的时间复杂性。

Answer 3

我想你念错到一定程度。 对于密集图形，关于使用斐波纳契文章会谈与满口时间复杂度为O（E + V日志V），这是显著更好。