为什么执行 n union find (union by size) 操作的时间复杂度是 O(n log n)？
Why is the time complexity of performing n union find (union by size) operations O(n log n)?
在联合查找操作的基于树的实现中，每个元素都存储在一个节点中，该节点包含一个指向集合名称的指针。集合指针指向 v 的节点 v 也是一个集合名。每个集合都是一棵树，以具有自引用集合指针的节点为根。
要执行合并，我们只需让一棵树的根指向另一棵树的根。为了执行查找，我们从起始节点开始跟踪集合名称指针，直到到达其集合名称指针指向自身的节点。
In Union by size -> 执行并集时，我们生成较小树的根
指向较大的根。这意味着 O(n log n) 时间
执行 n 个联合查找操作。每次我们跟随一个指针，我们都会到达一个大小至多为前一个子树大小两倍的子树。因此，对于任何查找，我们将最多遵循 O(log n) 个指针。
我不明白每个联合操作如何，查找操作总是 O(log n)。有人可以解释一下最坏情况下的复杂度是如何实际计算的吗？
让我们暂时假设，每棵高度为 h 的树至少包含 2^h 个节点。如果你加入两棵这样的树会发生什么？
如果它们的大小不同，则合并树的高度与更高的树的高度相同，因此新树仍然有2^h个节点（相同高度但节点更多）。
现在如果它们的高度相同，生成的树的高度将增加一，并且至少包含 2^h + 2^h = 2^(h+1) 个节点。所以条件仍然成立。
最基本的树（1个节点，高度0）也满足条件。因此，所有可以通过将两棵树连接在一起构建的树也满足它。
现在高度就是查找过程中要遵循的最大步数。如果一棵树有 n 个节点和高度 h (n >= 2^h) 这立即给出 log2(n) >= h >= steps.
您可以执行复杂度为 O(n lg* n) 的 n 联合查找（按等级或大小联合）操作，其中 lg* n 就是 inverse Ackermann function using path compression optimization.
注意 O(n lg* n) 优于 O(n log n)
在问题 Why is the Ackermann function related to the amortized complexity of union-find algorithm used for disjoint sets? 中，您可以找到有关此关系的详细信息。
我们需要证明树的最大高度是 log(N)，其中 N 是 UF 中的项目数 (1)
在基本情况下，所有树的高度都是0。(1)当然满足
现在假设所有的树都满足 (1) 我们需要证明将任意 2 棵树与 i, j (i <= j) 个节点连接起来将创建一棵最大高度为 log(i + j)(2):
因为连接 2 棵树的过程获取较小树的根节点并将其附加到较大树的根节点，所以新树的高度将为：
max(log(j), 1 + log(i)) = max(log(j), log(2i)) <= log(i + j) => (2) proved
- log(j): 新树的高度仍然是大树的高度
- 1 + log(i): 当两棵树的高度相同时
详情见下图：
参考：书 Algorithms
在联合查找操作的基于树的实现中，每个元素都存储在一个节点中，该节点包含一个指向集合名称的指针。集合指针指向 v 的节点 v 也是一个集合名。每个集合都是一棵树，以具有自引用集合指针的节点为根。
要执行合并，我们只需让一棵树的根指向另一棵树的根。为了执行查找，我们从起始节点开始跟踪集合名称指针，直到到达其集合名称指针指向自身的节点。
In Union by size -> 执行并集时，我们生成较小树的根 指向较大的根。这意味着 O(n log n) 时间 执行 n 个联合查找操作。每次我们跟随一个指针，我们都会到达一个大小至多为前一个子树大小两倍的子树。因此，对于任何查找，我们将最多遵循 O(log n) 个指针。
我不明白每个联合操作如何，查找操作总是 O(log n)。有人可以解释一下最坏情况下的复杂度是如何实际计算的吗？
让我们暂时假设，每棵高度为 h 的树至少包含 2^h 个节点。如果你加入两棵这样的树会发生什么？
如果它们的大小不同，则合并树的高度与更高的树的高度相同，因此新树仍然有2^h个节点（相同高度但节点更多）。
现在如果它们的高度相同，生成的树的高度将增加一，并且至少包含 2^h + 2^h = 2^(h+1) 个节点。所以条件仍然成立。
最基本的树（1个节点，高度0）也满足条件。因此，所有可以通过将两棵树连接在一起构建的树也满足它。
现在高度就是查找过程中要遵循的最大步数。如果一棵树有 n 个节点和高度 h (n >= 2^h) 这立即给出 log2(n) >= h >= steps.
您可以执行复杂度为 O(n lg* n) 的 n 联合查找（按等级或大小联合）操作，其中 lg* n 就是 inverse Ackermann function using path compression optimization.
注意 O(n lg* n) 优于 O(n log n)
在问题 Why is the Ackermann function related to the amortized complexity of union-find algorithm used for disjoint sets? 中，您可以找到有关此关系的详细信息。
我们需要证明树的最大高度是 log(N)，其中 N 是 UF 中的项目数 (1)
在基本情况下，所有树的高度都是0。(1)当然满足
现在假设所有的树都满足 (1) 我们需要证明将任意 2 棵树与 i, j (i <= j) 个节点连接起来将创建一棵最大高度为 log(i + j)(2):
因为连接 2 棵树的过程获取较小树的根节点并将其附加到较大树的根节点，所以新树的高度将为：
max(log(j), 1 + log(i)) = max(log(j), log(2i)) <= log(i + j) => (2) proved
- log(j): 新树的高度仍然是大树的高度
- 1 + log(i): 当两棵树的高度相同时
详情见下图：
参考：书 Algorithms