坚持用O表示法

Question

我正在比较两种算法,Prim和Kruskal.

我理解时间复杂性的基本概念以及两者最佳工作时(稀疏/密集图)

我在互联网上找到了这个,但我很难将其转换为英语.

dense graph:  Prim = O(N2)
              Kruskal = O(N2*log(N))

sparse graph: Prim = O(N2)
              Kruskal = O(N log(N))

这是一个很长的镜头,但任何人都可以解释这里发生了什么？

Answer 1

Prim是O(N ^ 2),其中N是顶点的数量.

Kruskal是O(E log E),其中E是边数."E log E"来自对边缘进行排序的好算法.然后,您可以在线性E时间处理它.

在密集图中,E~N ^ 2.因此Kruskal将是O(N ^ 2 log N ^ 2),其简单地为O(N ^ 2 log N).