Prim算法时间复杂度

Question

我查看了普里姆算法的Wikipedia entry，我注意到它对于邻接矩阵的时间复杂度是O(V^2)，对于堆和邻接表的时间复杂度是O(E lg(V))，其中E是边的数量，V是图中的顶点数量。

由于Prim算法用于更密集的图，E可以接近V^2，但当它这样做时，堆的时间复杂度变为O(V^2Lg(V))，它大于O(V^2)。显然，堆将提高性能，而不仅仅是搜索数组，但时间复杂性说明了另一种情况。

算法实际上是如何在改进的情况下减速的？

Answer 1

尽管堆使您不必搜索数组，但它减慢了算法的“更新”部分:数组更新为O(1)，而堆更新为O(log(N))。

从本质上讲，你在算法的一个部分中牺牲了速度，在另一部分中换取了速度。

无论如何，你必须搜索N次。然而，在密集图中，您需要更新很多(~V^2)，而在稀疏图中，您不需要更新。

另一个我想不到的例子是在数组中搜索元素。如果你只做一次，线性搜索是最好的-但如果你做了很多查询，最好对它进行排序，每次都使用二进制搜索。

Answer 2

我想你在某种程度上看错了。对于密集图，本文讨论了使用时间复杂度为O(E +V log V)的Fibonacci堆，这明显更好。