algorithm - 卡在O符号上

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

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

我在Internet上找到了它，但是我正在努力将其转换为英语。

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

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

这是一个很长的路要走，但是任何人都可以解释这里发生了什么吗？

最佳答案

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

关于algorithm - 卡在O符号上，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/1907929/