Prim的算法时间复杂度

我在Wikipedia条目中查找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），而在稀疏图中，则不需要更新。

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