相关疑难解决方法(0)

在联合查找操作的基于树的实现中，每个元素都存储在一个节点中，该节点包含指向集合名称的指针。集合指针指向 v 的节点 v 也是集合名称。每个集合都是一棵树，以具有自引用集合指针的节点为根。

要执行并集，我们只需使一棵树的根指向另一棵树的根即可。为了执行查找，我们从起始节点开始跟踪集合名称指针，直到到达集合名称指针引用自身的节点。

在按大小并集 -> 执行并集时，我们使较小树的根指向较大树的根。这意味着执行 n 个并集查找操作的时间为 O(n log n)。每次我们跟随一个指针，我们都会到达一个大小最多是前一个子树大小两倍的子树。因此，对于任何查找，我们最多都会遵循 O(log n) 个指针。

我不明白为什么对于每个联合操作，查找操作总是 O(log n)。有人可以解释一下最坏情况的复杂度是如何实际计算的吗？

在一个用于分析算法的类中,我们为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) …