使用优先级队列的Prims算法的复杂度？

Question

我用的是邻接矩阵，优先队列是数据结构。

根据我的计算，复杂度为V^3 log V：

• 同时循环：V
• 检查相邻顶点：V
• 检查队列是否条目已经存在，并更新相同的：V log v

但是，我到处都读到复杂性是V^2

请解释。

Answer 1

在优先级队列的情况下，如果不使用二进制堆，它包括两个基本步骤:1 .插入使用插入排序算法的插入时间复杂度是O(E^2)。删除删除对每个出列取O(1 ),并且出列等于顶点的数量，如果使用映射，否则将几乎相同，所以，这里的总时间复杂度是O(V E^2)

Answer 2

使用基于最小堆的优先级队列，时间复杂度为O（ElogV）。

正如您所说，外部while循环是O（V），因为它循环通过每个顶点，因为每个顶点都需要添加到MST一次。

对于 while 循环中考虑的每个顶点，需要执行以下两个步骤：

>

选择下一条边添加到MST。根据基于最小堆的优先级队列的属性，根元素始终是最小的元素。因此，选择下一条边，即成本最低的边，将是根元素的O（1）提取。在提取之后，需要以保持优先级队列的方式移动剩余值。由于队列表示一个平衡的二叉树，在最坏的情况下，这种移位可能发生在O（logV）中。

优先级队列已更新。入射到新顶点的边可能需要在队列中更新其成本，因为我们现在将考虑与新添加的顶点与其相邻点之间的边相关的成本（但是，如果它们通过成本低于新引入的边的边与以前添加的顶点相邻，则成本不会更新，因为我们正在寻找最低成本）。同样，这将是O（logV），因为在最坏的情况下，顶点将需要在表示队列的平衡二叉树的整个长度上移动。

步骤 1 发生 V 次，因为它在 while 循环中发生一次，所以它是 O（VlogV） 总计，步骤 2 发生在最坏的情况下 E 次，其中每个边都连接到当前顶点，因此它们都需要更新，这意味着它是 O（ElogV） 总计。设置为 O（E），因为它要求将优先级队列中的每个边缘成本初始化为无穷大。

使用基于最小堆的Priroty队列的总时间复杂度=O（E VlogV ElogV）=O（ElogV）

当您阅读复杂度为O（V^2）时，您可能会看到不使用堆的实现。在这种情况下，外部while循环仍然是O（V）。瓶颈在于选择下一个要添加到MST的顶点的步骤，即O（V），因为您需要检查与每个相邻节点相关的成本以找到最低成本，这在最坏的情况下意味着检查所有其他节点。因此复杂性为O（V*V）=O（V^2）。

此外，在非常密集的图中，O（ElogV）变为O（V^2），因为在任何图中，总边数最多可以有E = V^2。

Answer 3

如果使用斐波纳契堆，则提取min是< code>O(lg V)摊销成本，更新其中的条目是< code>O(1)摊销成本。

如果我们用这个伪代码

while priorityQueue not empty
    u = priorityQueue.exractMin()
    for each v in u.adjacencies
        if priorityQueue.contains(v) and needsWeightReduction(u, v)
            priorityQueue.updateKeyWeight(u, v)

假设实现对于< code > priority queue . contains(v)和< code > needsweightcreduction(u，v)都具有恒定的时间。

需要注意的是，为了检查邻接，可以稍微收紧绑定。虽然外循环运行＜code＞V

所以，你有外循环V次，内循环E次。提取最小运行次数＜code＞V

  V*lgV + E*1
= O(V lgV + E)

同样，由于E

  O(V lgV + V^2)
= O(V^2)

但是，在考虑稀疏图时，这是一个较宽松的界限（尽管是正确的）。