目录

  1. 基于 size 优化的基本概念
  2. 按大小合并的步骤
  3. 时间复杂度分析
  4. 代码示例（伪代码）
  5. 参考资料

1. 基于 size 优化的基本概念

在并查集中，合并操作可能导致树高增加，影响查找效率。基础实现随意合并两个集合，可能退化为链表，查找复杂度变为 O(n)。
基于 size 的优化通过记录每个集合的大小（节点数），在合并时总是将较小的集合连接到较大集合的根下，从而控制树高，提高效率。

2. 按大小合并的步骤

按大小合并使用“size”数组记录每个集合的节点数，具体步骤如下：

  1. 找到根节点：
  • 对两个元素 x 和 y，分别调用 Find 操作找到其根节点 rootX 和 rootY。
  1. 比较大小：
  • 检查 rootX 和 rootY 对应的集合大小（size[rootX] 和 size[rootY]）。
  1. 合并规则：
  • 如果 size[rootX] < size[rootY]：将 rootX 指向 rootY，更新 size[rootY]。
  • 如果 size[rootX] ≥ size[rootY]：将 rootY 指向 rootX，更新 size[rootX]。
  1. 更新大小：
  • 新根的 size 等于两个集合大小之和。

示例

初始：1, 2, 3 独立，size[1] = 1, size[2] = 1, size[3] = 1。

  • Union(1, 2)：
  • size[1] = 1, size[2] = 1，相等。
  • 设 1 为根，parent[2] = 1，size[1] = 2。
  • 结果：1 ← 2，size[1] = 2, size[2] = 1。
  • Union(1, 3)：
  • size[1] = 2, size[3] = 1。
  • parent[3] = 1，size[1] = 3。
  • 结果：1 ← 2, 1 ← 3，size[1] = 3。

3. 时间复杂度分析

  • 单次合并：
  • 未优化：O(h)，h 为树高，最差 O(n)。
  • 按大小合并后：O(1)（不含查找时间）。
  • 查找影响：
  • 树高被限制为 O(log n)，因为每次合并时较小集合加入较大集合，高度增长缓慢。
  • 总复杂度（m 次操作，n 个元素）：
  • 仅按大小合并：O(m * log n)。
  • 结合路径压缩：O(m * α(n))，α(n) 是阿克曼函数反函数，近似常数。
  • 空间复杂度：O(n)，需存储父节点和 size 数组。

4. 代码示例（伪代码）

class UnionFind:
    parent[]      // 父节点数组
    size[]        // 集合大小数组
    n             // 元素总数

    // 初始化
    function init(n):
        this.n = n
        for i = 0 to n-1:
            parent[i] = i
            size[i] = 1

    // 查找（简单版）
    function find(x):
        while parent[x] != x:
            x = parent[x]
        return x

    // 合并（按大小）
    function union(x, y):
        rootX = find(x)
        rootY = find(y)
        if rootX != rootY:
            if size[rootX] < size[rootY]:
                parent[rootX] = rootY
                size[rootY] = size[rootY] + size[rootX]
            else:
                parent[rootY] = rootX
                size[rootX] = size[rootX] + size[rootY]

5. 参考资料

如果你需要结合路径压缩的完整优化版本，或特定语言实现，请告诉我！