第148页 | 算法技术手册 | 阅读 ‧ 电子书库

同步阅读进度,多语言翻译,过滤屏幕蓝光,评论分享,更多完整功能,更好读书体验,试试 阅读 ‧ 电子书库

分析

Prim算法首先将所有的顶点插入到优先队列(二叉堆实现)中,时间开销为O(V log V)。然后decreaseKey操作将需要O(log q)的时间,q是优先队列中顶点的数目,q将会小于|V|。这个操作最多需要执行2*|E|次,在这种情况下,每一个顶点都会从优先队列中删除,图中的每一条边都会被访问两次。因此总性能是O((V+2*E)*log n)或者O((V+E)*log V)。

请支持我们,让我们可以支付服务器费用。
使用微信支付打赏


上一页 · 目录下一页


下载 · 书页 · 阅读 ‧ 电子书库