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

发布时间：2020-12-15 00:38:20 所属栏目：Java 来源：网络整理

导读：我使用的是邻接矩阵,优先级队列是数据结构. 根据我的计算,复杂度为V ^ 3 log V： while循环：V 检查相邻的顶点：V 如果条目已存在,则检查队列,并更新相同的内容：V log v 但是,我到处都读到复杂性是V ^ 2 请解释. 解决方法如果您使用Fibonacci堆,则提取min

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

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

> while循环：V
>检查相邻的顶点：V
>如果条目已存在,则检查队列,并更新相同的内容：V log v

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

请解释.

解决方法

如果您使用Fibonacci堆,则提取min是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次.提取min运行V次,并且更新堆中的条目运行E次.

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

同样,由于E< = V ^ 2,你可以用这个事实来代替和得到

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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!