algorithm - Prim 算法时间复杂度

Question

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

由于 Prim 的算法用于更密集的图，E 可以接近 V^2，但是当它接近时，堆的时间复杂度变为 O(V^2 lg(V)) 大于 O(V^2 ).显然，堆会比仅搜索数组提高性能，但时间复杂度则不然。

算法实际上是如何随着改进而变慢的？

Answer 1

即使堆使您免于搜索数组，它也会减慢算法的“更新”部分:数组更新为 O(1)，而堆更新为 O(log(N))。

本质上，您用算法一部分的速度换取另一部分的速度。

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

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