rom*_*ego 6 algorithm graph-theory time-complexity graph-algorithm union-find
在联合查找操作的基于树的实现中，每个元素都存储在一个节点中，该节点包含指向集合名称的指针。集合指针指向 v 的节点 v 也是集合名称。每个集合都是一棵树，以具有自引用集合指针的节点为根。
要执行并集，我们只需使一棵树的根指向另一棵树的根即可。为了执行查找，我们从起始节点开始跟踪集合名称指针，直到到达集合名称指针引用自身的节点。
在按大小并集 -> 执行并集时，我们使较小树的根指向较大树的根。这意味着执行 n 个并集查找操作的时间为 O(n log n)。每次我们跟随一个指针，我们都会到达一个大小最多是前一个子树大小两倍的子树。因此，对于任何查找，我们最多都会遵循 O(log n) 个指针。
我不明白为什么对于每个联合操作，查找操作总是 O(log n)。有人可以解释一下最坏情况的复杂度是如何实际计算的吗？
Hen*_*nry 11
我们暂时假设每棵高度为 h 的树至少包含 2^h 个节点。如果你连接两棵这样的树会发生什么？
如果它们的高度不同，则合并后的树的高度与较高的树的高度相同，因此新树仍然具有超过 2^h 个节点（高度相同但节点更多）。
现在，如果它们的高度相同，则生成的树的高度将增加一，并且将包含至少 2^h + 2^h = 2^(h+1) 个节点。所以条件仍然成立。
最基本的树（1 个节点，高度 0）也满足条件。因此，所有可以通过将两棵树连接在一起构建的树也满足它。
现在，高度只是查找期间要遵循的最大步骤数。如果一棵树有 n 个节点且高度为 h (n >= 2^h)，则立即给出 log2(n) >= h >= 步数。
您可以执行 n 并集查找（按等级或大小并集）操作，复杂度为O(n lg* n)，其中lg* n是使用路径压缩优化的逆阿克曼函数。
请注意，O(n lg* n)优于O(n log n)
在问题中，为什么阿克曼函数与用于不相交集的并查找算法的摊余复杂度相关？您可以找到有关此关系的详细信息。