为什么使用逆阿克曼函数来描述 Kruskal 算法的复杂性？
Why is the Inverse Ackermann function used to describe complexity of Kruskal's algorithm?
在用于算法分析的 class 中，我们看到了 Kruskal 算法的伪代码：
然后他针对不相交的森林陈述如下：
A sequence of m MAKE-SET, UNION, and FIND-SET operations, n of which
are MAKE-SET operations, can be performed on a disjoint-set forest
with union by rank and path compression in worst-case time O(m α(n)).
Used to compute the complexity of Step 2, and steps 5-8
For connected G: |E| ≥ |V| -1; m = O(V + E), n = O(V);
So Steps 2, 5-8: O((V + E) α(V)) = O(E α(V))
α(V) = O(lg V) = O(lg E); so we obtain O(E lg E) ----- // how is α(V) equal here?
Kruskal: Steps 3, 5-8, and step 4: O(E lg E)
观察：|E| < |V|2 -> lg E = O(lg V)
所以，Kruskal 复杂度：O(E lg V)
我试图理解这个 "alpha(n)"/"α(n)" 函数背后的逻辑，从我读到的内容来看，简单地说，Ackermann 函数是一个令人难以置信的指数增长的函数快，反之则以对数方式非常缓慢地增长。
如果我的解释是正确的，那么“α(n)”代表什么？这是否意味着 MAKE-SET 操作至多为 O(lg n)？ How/Why 是否需要使用逆阿克曼？我的印象是这个操作执行了 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) = O(lg V) 是一种常见的符号滥用，实际上我们有 α(V) ∈ O(lg V)（V 的逆阿克曼是函数集 O 的成员（LG V））。它们不相等，它们甚至不是同一类型，一个是一个函数，另一个是一组函数。
how is it known that that |E| < |V|²?
一个完整的无向图有多少条边？你不能拥有更多。您可以在多图中进行操作，但这不是算法所依据的，并且将其扩展到多图中是没有用的 - 只需丢弃除了一对节点之间的最佳边之外的所有边。
why is it that a "forest" representation of disjoint sets seems to be more efficient than those implemented with linked lists when my lecturer states they are both O(E log V)?
出于几个原因，这是一件很奇怪的事情。首先，您是通过 Kruskals 算法而不是它自己有效地测量不相交集的效率。 "they" 你的问题是 Kruskals 算法的两种实现。其次，正如您肯定意识到的那样，上界的推导使用了 α(V) ∈ O(lg V)。所以它故意忽略了一个显着的差异。这是有道理的，因为时间复杂度逐渐由排序步骤决定，但仅仅因为差异在大 O 中是不可见的并不意味着它不存在。
Therefore is there a point in the increased difficulty of implementing disjoint sets with forests?
确实没有增加难度。这是一个超级简单的数据结构，您可以在 5 分钟内编写，只需两个数组和一些简单的代码 - 链表实际上可能更难，特别是如果您必须进行手动内存管理。请注意，在 Kruskals 算法的上下文之外，渐近时间和实际时间的差异是巨大的。
但即使在 Kruskals 算法的背景下，改进算法的第二阶段显然会使总时间更好，即使它没有显示在最坏情况下的渐近时间。 FWIW 你也可以改进第一阶段，你可以使用堆（或者它的一个更高级的替代品）并且在线性时间内只 heapify 边缘。然后算法的第二阶段将一个一个地提取它们，但至关重要的是，您通常不必提取 每个 边 - 您可以跟踪剩下多少个不相交的集合，当它下降到 1 时停止，可能会留下许多（甚至大多数）未使用的边缘。在最坏的情况下这无济于事，但在现实生活中却有帮助。在特殊情况下，当应用任何快速排序（计数排序、桶排序等）时，您可以比 O(E log E) 更快地对边进行排序。
在用于算法分析的 class 中，我们看到了 Kruskal 算法的伪代码：
然后他针对不相交的森林陈述如下：
A sequence of m MAKE-SET, UNION, and FIND-SET operations, n of which are MAKE-SET operations, can be performed on a disjoint-set forest with union by rank and path compression in worst-case time O(m α(n)).
Used to compute the complexity of Step 2, and steps 5-8
For connected G: |E| ≥ |V| -1; m = O(V + E), n = O(V);
So Steps 2, 5-8: O((V + E) α(V)) = O(E α(V))
α(V) = O(lg V) = O(lg E); so we obtain O(E lg E) ----- // how is α(V) equal here?
Kruskal: Steps 3, 5-8, and step 4: O(E lg E)
观察：|E| < |V|2 -> lg E = O(lg V)
所以，Kruskal 复杂度：O(E lg V)
我试图理解这个 "alpha(n)"/"α(n)" 函数背后的逻辑，从我读到的内容来看，简单地说，Ackermann 函数是一个令人难以置信的指数增长的函数快，反之则以对数方式非常缓慢地增长。
如果我的解释是正确的，那么“α(n)”代表什么？这是否意味着 MAKE-SET 操作至多为 O(lg n)？ How/Why 是否需要使用逆阿克曼？我的印象是这个操作执行了 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) = O(lg V) 是一种常见的符号滥用，实际上我们有 α(V) ∈ O(lg V)（V 的逆阿克曼是函数集 O 的成员（LG V））。它们不相等，它们甚至不是同一类型，一个是一个函数，另一个是一组函数。
how is it known that that |E| < |V|²?
一个完整的无向图有多少条边？你不能拥有更多。您可以在多图中进行操作，但这不是算法所依据的，并且将其扩展到多图中是没有用的 - 只需丢弃除了一对节点之间的最佳边之外的所有边。
why is it that a "forest" representation of disjoint sets seems to be more efficient than those implemented with linked lists when my lecturer states they are both O(E log V)?
出于几个原因，这是一件很奇怪的事情。首先，您是通过 Kruskals 算法而不是它自己有效地测量不相交集的效率。 "they" 你的问题是 Kruskals 算法的两种实现。其次，正如您肯定意识到的那样，上界的推导使用了 α(V) ∈ O(lg V)。所以它故意忽略了一个显着的差异。这是有道理的，因为时间复杂度逐渐由排序步骤决定，但仅仅因为差异在大 O 中是不可见的并不意味着它不存在。
Therefore is there a point in the increased difficulty of implementing disjoint sets with forests?
确实没有增加难度。这是一个超级简单的数据结构，您可以在 5 分钟内编写，只需两个数组和一些简单的代码 - 链表实际上可能更难，特别是如果您必须进行手动内存管理。请注意，在 Kruskals 算法的上下文之外，渐近时间和实际时间的差异是巨大的。
但即使在 Kruskals 算法的背景下，改进算法的第二阶段显然会使总时间更好，即使它没有显示在最坏情况下的渐近时间。 FWIW 你也可以改进第一阶段，你可以使用堆（或者它的一个更高级的替代品）并且在线性时间内只 heapify 边缘。然后算法的第二阶段将一个一个地提取它们，但至关重要的是，您通常不必提取 每个 边 - 您可以跟踪剩下多少个不相交的集合，当它下降到 1 时停止，可能会留下许多（甚至大多数）未使用的边缘。在最坏的情况下这无济于事，但在现实生活中却有帮助。在特殊情况下，当应用任何快速排序（计数排序、桶排序等）时，您可以比 O(E log E) 更快地对边进行排序。