5

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

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

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

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

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

这有点长镜头，但任何人都可以解释这里发生了什么？

4

6 回答 6

5

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

于 2009-12-15T14:57:30.373 回答
3

好的，这就去。O(N2) (2 = squared) 意味着大 N 的算法速度随 N 的平方而变化 - 因此两倍的图形大小将导致四倍的计算时间。

Kruskal 行只是简化了，并假设E = c * N2. c这里大概是一个常数，当 N 变大时，我们可以假设它明显小于 N。您需要了解以下对数定律：log(ab) = log a + log b和log(a^n) = n * log a。这两者结合 log c << log N （远小于并且可以忽略）应该让您理解那里的简化。

现在，至于原始表达式以及它们的来源，您需要检查您从中获得这些的页面。但是我假设如果您正在查看 Prim 和 Kruskal 的，那么您将能够理解推导，或者至少如果您无法向您解释，从长远来看实际上不会对您有所帮助...

于 2009-12-15T14:56:00.187 回答
2

Kruskal 对图中的边数 (E) 敏感，而不是节点数。然而，Prim 仅受节点数 (N) 的影响，计算结果为O(N^2)。

这意味着在边数接近 N^2（所有节点连接）的密集图中，它的复杂度因子O(E*log(E))大致相当于O(N^2*log(N)).

c 是解释“几乎”的常数，与 O 表示法无关。此外，log(N^2) 与 log(N) 的数量级相同，因为对数大大超过了 2 的幂（log(N^2) => 2*log(N)在 O 表示法中是O(log(N))）。

在稀疏图中 E 更接近 N 给你O(N*log(N))。

于 2009-12-15T14:57:13.727 回答
1

这两种算法为不同的输入（节点和边）定义了 big-O。所以他们正在将一个转换为另一个来比较它们。

N 是图中的节点数 E 是边数。

对于密集图，有 O(N^2) 条边

对于稀疏图，有 O(N) 条边。

常数对于 big-O 当然是无关紧要的，因此 c 退出

于 2009-12-15T14:56:05.270 回答
1

想法是，在密集图中，边数为 O(N^2)，而在稀疏图中，边数为 O(N)。因此，他们采用 O(E \lg E) 并用 E 的近似值对其进行扩展，以便直接将其与 Prim 的 O(N^2) 的运行时间进行比较。

基本上，它表明 Kruskal 更适合稀疏图，而 Prim 更适合密集图。

于 2009-12-15T14:56:07.660 回答
0

首先：n 是顶点的数量。

Prim 是 O(n^2) 这部分很容易。

Kruskal 是 O(Elog(E))，其中 E 是边数。在一个稠密的图中，有多达 N 个选择 2 条边，大约是 n^2（实际上是 n(n-1)/2，但是谁在数呢？）所以，大约是 n^2 log (n^2 ) 这是 2n^2 log n 这是 O(n^2logn) 大于 O(n^2)

在稀疏图中，只有 n 条边，所以我们有 n log n，它小于 O(n^2)。

于 2009-12-15T14:59:54.923 回答