algorithm - Prim 算法时间复杂度

Question

我正在查看 Prim 算法的Wikipedia 条目，我注意到它与邻接矩阵的时间复杂度为 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)，而在稀疏图中，您不需要。

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

Answer 2

从算法导论（卡门）

时间= Θ(V)·T(EXTRACT-MIN) + Θ(E)·T(DECREASE-KEY)

                   T(EXTRACT-MIN) T(DECREASE-KEY) 总计

1. 数组 O(V) O(1) O(V^2)
2.二叉堆 O(lgV) O(lgV) O(E lgV)
3. 斐波那契堆 O(lgV) O(1) O(E + VlgV)

使用不同的数据结构会导致不同的时间复杂度。

Answer 3

我认为你在某种程度上读错了。对于密集图，文章讨论了使用时间复杂度为 O(E + V log V) 的斐波那契堆，这要好得多。