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

Question

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

根据我的计算，复杂度是 V^3 log V:

• While 循环: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) .

需要注意的是，您可以稍微严格地绑定(bind)以检查邻接关系。当外循环运行时 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)

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