上过了数据结构和算法课，但是百度的Prim算法这道题，答案不是O（elogv）吗？

Question

优化之前是O(eloge), 优化之后是O(elogv).

这道百度的题目答案怎么选择，如何理解？

谢谢老师。

Answer 1

提问者 new_chapter 2019-02-16 16:38:31

非常感谢老师详尽的回答！

在算法与数据结构课程中，您在讲解lazy prim算法（存边，未优化）时间复杂度时，外层循环 while(!pq.isEmpty()) ，循环次数为边数E。内层包括两个部分：

1. 从堆中取出最小的边 pq.extractMin(), 时间复杂度为logE

2. visit 函数，把所有的visit对邻边的遍历合在一起，也是E次（邻接矩阵V^2次），每次执行pq.insert()函数，复杂度为logE。

综合起来是 O(ElogE + ElogE ), 也就是 O(ElogE)。

（E+V）logE是如何得出的呢？我是在哪里理解的不到位？

对于优化过的lazy prim，用最小索引堆实现。外层循环优化为V次，内层

1. 对堆的操作extractMin优化为logV

2. visit 对所有的顶点的临边进行遍历，总共对索引堆的操作（insert 和 change )应该是小于E次的。但也是E这个级别。所以复杂度为(E+V)logV, 综合复杂度为ElogV。

您的回答中提到，没有优化的prim算法，复杂度可以到O(V*E),对于临界矩阵表示的稠密图，e=v^2。可以选择，O(E^3)。但是，题目中是临界表，好像没有正确的答案吧。

• liuyubobobo #1

  请把对prim算法探讨的进一步问题放在《算法与数据结构》课程中，谢谢。

Answer 2

liuyubobobo 2019-02-13 12:26:17

Prim算法在我的《算法与数据结构》课程中有详细的介绍：）https://coding.imooc.com/class/71.html

严格说，最优实现的Prim算法的时间复杂度是O((V+E)logV)的。

V+E的过程遍历整个图（图的便利的时间复杂度是O(V+E)的），同时维护一个堆，用于选择切分定理中横切边最短的边对应的那个没有被遍历的顶点。

（理解Prim算法的关键是理解切分定理！）

对于维护的这个堆，可以存边，可以存点。如果存边，复杂度就是O((V+E)logE)的，因为堆的每个操作是logE的（堆中最多存储所有的边）。在我的课程中，被称为Lazy Prim；

如果存点，实现上稍微复杂一些，需要借助索引堆，但是复杂度是O((V+E)logV)的。（堆中最多存储所有的点）。

不过，对于O((V+E)logV)这个时间复杂度，我们写成O(ElogV)也是没有问题的。这是因为E的阶数肯定比V大（最大的情况，E是O(V^2)级别的），所以对于VlogV和ElogV两项，VlogV成为了低阶项。在大O表示下，可以省略。O((V+E)logV) = O(VlogV + ElogV) = O(ElogV)。

同理，Lazy Prim（未优化的Prim算法）也可以说是O(ElogE)的。

当然，这里说未优化，其实在大多数情况下，Lazy Prim的性能也是可以接受的。真要不优化，Prim也可以实现成O(V*E)级别的，就不在我们的讨论范围里了：）

以下结论来自我的《算法与数据结构》课程的PPT：）

继续加油！：）

• 提问者 new_chapter #1

  非常感谢老师的答复！
  
  直接在这里回复您，出来的文字没有格式，不方便您阅读。
  
  所以我把编辑的对您的回复 写在了“添加回答”中，希望老师可以帮我解惑。