3

在算法分析类中，我们看到了 Kruskal 算法的伪代码：

Kruskal 算法伪代码

然后，对于不相交的森林，他陈述了以下内容：

在最坏情况时间O(m α (n))。

用于计算步骤 2 和步骤 5-8 的复杂度

对于连接的 G：|E| ≥ |V| -1; m = O(V + E)，n = O(V)；

所以步骤 2、5-8：O((V + E) α(V)) = O(E α(V))

α(V) = O(lg V) = O(lg E)；所以我们得到 O(E lg E) ----- // 这里的 α(V) 怎么相等？

Kruskal：第 3、5-8 步和第 4 步：O(E lg E)

观察：|E| < |V|2 -> lg E = O(lg V)

所以，克鲁斯卡尔复杂度：O(E lg V)

我试图理解这个“alpha(n)”/“α(n)”函数背后的逻辑，从我所读到的内容来看，简单地说，Ackermann 函数是一个以令人难以置信的速度增长的函数，并且inverse 是一种以对数方式缓慢增长的方法。

如果我的解释是正确的，“α(n)”代表什么？这是否意味着 MAKE-SET 操作最多为 O(lg n)？如何/为什么需要使用逆阿克曼？我的印象是这个操作执行了 V 次（对于每个顶点）。在此之后，α(V) 也被简化为 O(lg V) = O(lg E)，这是否意味着，α(V) 最多可以表示为 O(lg V)？

另外，为什么|E| < |V|^2 -> lg E = O(lg V)语句，怎么知道 |E| < |V|^2?

我认为我的问题真的归结为，为什么当我的讲师说它们都是 O(E log V) 时，不相交集的“森林”表示似乎比使用链表实现的那些更有效？因此，与森林实施不相交集的难度增加有什么意义吗？

4

1 回答 1

10

α(V) = O(lg V) 是一种常见的符号滥用，实际上我们有 α(V) ∈ O(lg V) （V 的逆阿克曼是函数集 O(lg V) 的成员） . 它们不相等，甚至不是同一类型，一个是函数，另一个是一组函数。

怎么知道 |E| < |V|²?

一个完整的无向图有多少条边？你不能拥有更多。你可以在多重图中，但这不是算法所操作的，将它扩展到多重图是没有用的 - 只是扔掉除了一对节点之间的最佳边缘之外的所有边缘。

为什么当我的讲师说它们都是 O(E log V) 时，不相交集的“森林”表示似乎比使用链表实现的更有效？

出于几个原因，这是一件奇怪的事情。首先，您通过 Kruskals 算法而不是通过它自己有效地测量不相交集的效率。“他们”是你的问题是 Kruskals 算法的两种实现。其次，正如你肯定意识到的那样，上界的推导使用了 α(V) ∈ O(lg V)。所以它故意忽略了一个显着的差异。这是有道理的，因为时间复杂度由排序步骤渐近支配，但仅仅因为在大 O 中不可见差异并不意味着它不存在。

因此，与森林实施不相交集的难度增加有什么意义吗？

真的没有增加难度。这是一个超级简单的数据结构，你可以在 5 分钟内编写，只需两个数组和一些简单的代码 - 链表实际上可能更难，特别是如果你必须进行手动内存管理。请注意，在 Kruskals 算法的上下文之外，在渐近时间和实际时间方面的差异是巨大的。

但即使在 Kruskals 算法的上下文中，改进算法的第二阶段显然会使总时间更好，即使它在最坏情况下没有表现出渐近时间。FWIW，您也可以改进第一阶段，您可以使用堆（或其中一个更高级的替代品）并且只在线性时间内堆化边缘。然后算法的第二阶段将一个一个地提取它们，但至关重要的是，您通常不必提取每个边缘 - 您可以跟踪剩下多少不相交的集合并在它下降到 1 时停止，可能会留下许多（甚至大多数）边缘未使用。在最坏的情况下这无济于事，但在现实生活中确实如此。在特殊情况下，当任何快速排序（计数排序、桶排序等）适用时，您可以比 O(E log E) 更快地对边进行排序。

于 2017-06-04T14:49:51.460 回答