为什么逆Ackermann函数用于描述Kruskal算法的复杂性？
Ben*_*mer 1 algorithm complexity-theory graph-theory ackermann kruskals-algorithm
在一个用于分析算法的类中,我们为Kruskal算法提供了这个伪代码:
然后他说明了以下不相交的森林:
m个MAKE-SET,UNION和FIND-SET操作的序列,其中n个是MAKE-SET操作,可以在不相交的森林上执行,在最坏情况下的时间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)
所以,Kruskal的复杂性:O(E lg V)
我试图理解这个"alpha(n)"/"α(n)"函数背后的逻辑,从我所读到的看来,简单地说,Ackermann函数是指数速度快得令人难以置信的,而且逆是以对数方式非常缓慢地增长.
如果我的解释是正确的,"α(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)时,不相交集的"森林"表示似乎比链表实现的更有效？因此,与森林实施不相交集合的难度增加是否有意义？
α(V)= O(lg V)是一种常见的符号滥用,实际上我们有α(V)∈O(lg V)(V的反Ackerman是函数集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)更快地对边进行排序.