1

假设图 G 中的边权重均匀分布在 [0,1) 上。哪种算法 prims 或 Kruskals 会更快？我认为这将是 kruskals，因为我们可以利用特定的排序算法，因为排序是 kruskals 算法的瓶颈步骤。

4

3 回答 3

0

这是您必须进行基准测试的东西。您可以使用花哨的数据结构（van Emde Boas 树）和排序算法（一些计数排序变体）将两种算法的理论预期复杂度降低到更接近线性的程度。但是，尚不清楚任何此类技巧是否可以提高任一算法的实际性能。提高内存局部性的恶作剧可能会产生更大的影响。

于 2013-06-09T16:53:24.167 回答
0

边缘权重的分布无关紧要。

Prims 和 Kruskals 之间的主要区别在于 Prim 算法的运行时间与顶点数的平方成正比，而 Kruskal 算法的运行时间与边数和边数的对数的乘积成正比。因此，Prim 在密集图上更快，而 Kruskal 在稀疏图上更快。

例如，如果您有 1000 个顶点 3000 条边（稀疏），那么 Prim 将为 K1 * 1,000,000，而 Kruskal 将为 K2 * 24,000。但是如果你有 1000 个顶点和 250,000 条边（密集），那么 Kruskal 将是 K2 * 3,100,000。

于 2013-06-09T17:31:59.503 回答
0

更新 2正如@David Eisenstat 在下面的评论中指出的那样，在 O(E) 时间内进行排序的更简单的方法是使用 |E| 进行存储桶排序。桶。区间 [0, 1) 可分为 |E| 长度为 1/|E| 的桶 每个，编号为 0、1、2 ... |E|-1，区间内的任何权重 w 都属于编号为 k = floor(|E| w) 的桶。每个桶中的预期权重数量为 O(1)，因此可以使用 |E| 进行排序 每个插入排序的大小为 O(1)，因此这给出了 O(E alpha(V)) 的预期时间 Kruskal 算法。

注意：作为@G。Bach 指出，上述假设可以在 O(1) 时间内执行权重和 floor(|E| w) 浮点乘法的比较，这可能需要一定的怀疑。对于非常大的 |E| 值，这两个操作可能仍然有 O(lg E) 的贡献。

更新正如 G. Bach 在下面指出的，第一轮 O(1) 数字的基数排序后的 bin 大小将始终为 Omega(E)，因此从技术上讲，以下答案不能保证在 O(E) 时间内排序。但是，可以选择小于 O(lg E) 的位数，或者 O(lg lg E) 或 O(sqrt lg E)？因此排序花费的时间少于 O(E lg E) 预期时间。

原始答案

这是 CLRS 中的练习 23.2-6。我很确定 Kruskal 会更快（因此这里的其他答案是错误的）。权重的分布很重要。无关紧要的是图形的密度/稀疏度。

普通版本主要由排序边缘权重的 O(E lg E) 时间决定。当边缘权重从均匀分布中提取时，我们可以对某个恒定位数执行基数排序，然后通过进一步的基数排序来修复连续子数组中的冲突。那是 O(E) 时间。

然后，剩下的只是普通的 Kruskal：使用具有联合秩和路径压缩的不相交集（如 CLRS 的第 23 章）剩余的工作是 O(E alpha(V))，其中 alpha(V) 是反 Ackermann 函数，并且对于任何正常的 V 值，它都 <= 4（认为数字比宇宙中的原子大得多）。

因此，对于基数排序，Kruskal 是线性 O(E)，概率任意接近 1。

基数排序注意事项：

通过使用更多的数字可以使预期的冲突数量（即前 15 位相同的边权重）任意小，但如果数字数量为 O(lg E)，则为 O(1)。当然，这意味着 O(E lg E) 基数排序，这会破坏目的。然而，我们实际上并不需要完全避免碰撞，只需限制它们的大小，以便它们可以在线性时间内修复。

因此，我们可以考虑在一个“轮”基数排序中对一些恒定位数（如 15）进行排序，这会将权重数组分成连续的子数组（也称为“bins”），所有子数组都具有相同的 15 个数字，然后在下一轮，使用第二“轮”基数排序对每个子数组的第 16-30 位进行排序。

正式证明将涉及与生日悖论类似的计算，但由于冲突的概率随着使用的附加数字的数量呈指数下降，所以应该可以使用 O(1)“轮数”对上述内容进行完全排序，这将导致O(E) 总排序时间。

于 2020-12-26T03:06:56.717 回答