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

Question

我使用的是邻接矩阵,优先级队列是数据结构.

根据我的计算,复杂性是V^3 log V:

• 循环: V
• 检查相邻的顶点: V
• 如果条目已存在则检查队列,并更新相同的队列: V log v

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

请解释.

Answer 1

如果您使用斐波那契堆，则提取最小值是O(lg V)摊销成本，更新其中的条目是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)

假设 和 的实现时间均为priorityQueue.contains(v)常数needsWeightReduction(u, v)。

需要注意的是，您可以稍微更紧地检查邻接关系。虽然外循环运行V多次，并且检查任何单个节点的邻接关系是最差的V操作，但您可以使用聚合分析来认识到您永远不会检查超过E邻接关系（因为只有 E 条边）。并且E <= V^2，所以这是一个稍微好一点的界限。

因此，您有外循环 V 次，内循环 E 次。提取最短运行V时间，并更新堆运行时间中的条目E。

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

再说一次，因为 E <= V^2你可以用这个事实来替换并得到

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

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