algorithm - 坚持使用 O 符号

Question

我正在比较两种算法，Prim 的和 Kruskal 的。

我了解时间复杂度的基本概念以及两者何时最有效(稀疏/密集图)

我在 Internet 上找到了这个，但我正在努力将其转换为英文。

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 )。