Prim的算法时间复杂度

我正在查看Prim算法的维基百科条目,我注意到它的邻接矩阵的时间复杂度是O(V ^ 2),它的堆和邻接列表的时间复杂度是O(E lg(V))其中E是边数和V是图中顶点的数量.

由于Prim的算法用于更密集的图,因此E可以接近V ^ 2,但是当它接近时,堆的时间复杂度变为O(V ^ 2 lg(V)),其大于O(V ^ 2).显然,堆只会在搜索数组时提高性能,但时间复杂性则另有说法.

算法如何通过改进实际减速？

即使堆使您无法搜索数组,也会减慢算法的"更新"部分:数组更新为O(1),而堆更新为O(log(N)).

实质上,您在算法的一部分中交换速度以在另一部分中交换速度.

无论如何,你都要搜索N次.但是,在密集图中,您需要更新很多(~V ^ 2),而在稀疏图中,则不需要.

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