为什么执行n个联合查找（按大小合并）操作O（n log n）的时间复杂度？

Question

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

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

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

我不了解每个联合操作的方式，查找操作始终为O（log n）。有人可以解释一下如何计算最坏情况下的复杂度吗？

Answer 1

目前，假设每个高度为h的树至少包含2 ^ h个节点。如果您加入两个这样的树会发生什么？

如果它们的大小不同，则合并树的高度与较高树的高度相同，因此新树的节点数仍大于2 ^ h（相同的高度，但节点数更多。）

现在，如果它们的高度相同，则结果树的高度将增加一，并且将包含至少2 ^ h + 2 ^ h = 2 ^（h + 1）个节点。因此条件仍然成立。

最基本的树（1个节点，高度0）也满足该条件。因此，可以通过将两棵树连接在一起来构建的所有树也都满足它。

现在，高度只是查找过程中要遵循的最大步骤数。如果树有n个节点且高度为h（n> = 2 ^ h），则立即给出log2（n）> = h> =步长。

Answer 2

[我们需要证明树的最大高度为log（N），其中N是UF (1)中的项数

在基本情况下，所有树的高度均为0。当然满足(1)

现在假设所有树都满足（1），我们需要证明将任意两棵树与i，j（i <= j）个节点连接将创建一个新树，其最大高度为log（i + j）(2)：

由于加入两棵树的过程将获取较小树的根节点并将其附加到较大树的根节点，因此新树的高度将为：

max(log(j), 1 + log(i)) = max(log(j), log(2i)) <= log(i + j) => (2) proved

请参见下面的图片以获取更多详细信息：

参考书：Algorithms

Answer 3

您可以进行n个具有复杂度O（n lg * n）]的联合查找（按等级或大小进行联合）操作，其中lg * n是inverse Ackermann function使用path compression optimization。

请注意，O（n lg * n）

比O（n log n）] >>>