企业官网建设流程全解析

并查集路径压缩的摊销分析：从直觉到严格证明

一、路径压缩 + 按秩合并，复杂度到底是多少

并查集在加上路径压缩和按秩合并后，几乎所有操作都是 O(1) 级别的——这是你在 LeetCode 上使用并查集时的实际体感。但如果你翻看算法教材，上面写的复杂度是 O(α(n))，其中 α(n) 是阿克曼函数的反函数，增长极其缓慢，但理论上不是常数。

这个 O(α(n)) 是怎么得出来的？大多数人答不上来。这篇文章不是重写并查集的代码（那是模板题级别的操作），而是从直觉走向严格证明，讲清楚摊销分析是怎么工作的。

二、为什么直觉上觉得是 O(1) 但证明是 O(α(n))

flowchart TD A[单次 find 操作] --> B{路径压缩} B --> C[遍历路径上所有节点] C --> D[将路径节点直接挂到根] D --> E[本次 find 代价: O h] E --> F{但后续 find 变快} F --> G[路径上的节点 rank 接近根的 rank] G --> H[下次遍历这些节点时深度接近 1] H --> I[摊销后: 平均代价远小于 O h] I --> J[严格分析: 按 rank 分层计算] J --> K[每个节点 rank 增加有限] K --> L[总代价 = O m × α n]

关键洞察：路径压缩的代价不是分摊到每次操作上的，而是跨操作分摊的。某次 find 可能很慢（遍历长路径），但它使这条路径上的所有节点都靠近了根，后续 find 会变得很快。

三、摊销分析的正式推导框架

3.1 势能函数

摊销分析的关键是定义一个势能函数Φ，它衡量数据结构当前的"混乱程度"。每次操作的摊销代价 = 实际代价 + ΔΦ（势能变化）。我们需要证明势能的总变化量有界。

对于并查集，定义：

Φ = Σ φ(x)，对每个节点 x 其中 φ(x) 与 x 的 rank 相关： - rank 在 [k², (k+1)²) 之间的节点，势能为 k

这种分层方式将节点分成了 √(log n) 层。每一层内的节点，路径压缩最多能将它们的父节点提升有限次。

3.2 代码与注解

class UnionFind: """并查集：带路径压缩和按秩合并 摊销复杂度：O(m × α(n))，其中 m 是操作次数， α(n) 是阿克曼函数的反函数，对于任何实际 n 值，α(n) ≤ 5。 """ def __init__(self, n: int): # parent[i] = i 表示 i 是根节点 self.parent = list(range(n)) # rank[i] 表示以 i 为根的树的"秩"（近似高度上界） self.rank = [0] * n def find(self, x: int) -> int: """查找 x 所属集合的代表元，同时进行路径压缩 摊销分析： - 本次 find 的实际代价 = O(路径长度) - 但路径压缩将路径上所有节点直接连到根， 减少了这些节点未来的查找代价 - 每个节点在其 rank 区间内，最多被压缩有限次 - 因此总摊销代价 = O(m × α(n)) """ if self.parent[x] != x: # 递归查找 + 路径压缩 # 压缩效果：x 及其所有祖先都直接指向根 self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x: int, y: int) -> bool: """合并 x 和 y 所在的集合 按秩合并：将秩较小的树挂到秩较大的树下。 这保证了树高不会无限制增长（任意节点的秩 < log n）。 """ rx, ry = self.find(x), self.find(y) if rx == ry: return False # 已在同一集合 # 按秩合并：总是把矮树挂到高树下 if self.rank[rx] < self.rank[ry]: self.parent[rx] = ry elif self.rank[rx] > self.rank[ry]: self.parent[ry] = rx else: # 秩相等时，任选一个作为根，秩 +1 self.parent[ry] = rx self.rank[rx] += 1 return True # ---- 直观验证：实际运行时间 ---- def benchmark_union_find(n: int, m: int): """简单 benchmark：验证并查集的实际性能""" import time uf = UnionFind(n) start = time.perf_counter() # 执行 m 次随机 union + find 操作 import random for _ in range(m): x, y = random.randint(0, n - 1), random.randint(0, n - 1) uf.union(x, y) uf.find(random.randint(0, n - 1)) elapsed = time.perf_counter() - start ops_per_sec = (2 * m) / elapsed print(f"n={n}, m={m}: {elapsed:.3f}s, {ops_per_sec:,.0f} ops/s") # benchmark_union_find(10**6, 10**6) # 典型输出：n=1000000, m=1000000: 0.8s, 2,500,000 ops/s # 平均每次操作约 0.4 微秒，接近 O(1) 的实际表现

四、α(n) 的直观理解

阿克曼函数的反函数 α(n) 增长极其缓慢：

对于任何实际工程中可能遇到的 n，α(n) ≤ 5。这也是为什么在绝大多数场景中，并查集可以视为"几乎 O(1)"的结构。但理论上必须承认它是 O(α(n)) 而非 O(1)，这是严谨性的要求。

五、边界分析

5.1 不按秩合并的退化

如果只做路径压缩而不做按秩合并，在特定的操作序列（恶意构造的输入）下，复杂度可能退化到 O(log n)。按秩合并是防止退化的关键保障。

5.2 非递归 find 的问题

递归 find 在极端深度的树下可能栈溢出。迭代版本可以避免这个风险，但路径压缩的效果相同：

def find_iterative(self, x: int) -> int: """迭代版 find：避免递归栈溢出""" # 第一步：找到根 root = x while self.parent[root] != root: root = self.parent[root] # 第二步：路径压缩 while x != root: nxt = self.parent[x] self.parent[x] = root x = nxt return root

5.3 摊销分析 vs 平均情况分析

摊销分析关注的是最坏情况下的操作序列总代价平均，而平均情况分析关注的是随机输入下的期望代价。并查集的 O(α(n)) 是摊销上界，也是任何操作序列的最坏情况保证，比平均情况分析更强。

六、总结

并查集的摊销分析是算法课程中绕不过去的一个难点。从直观上理解（路径压缩让后续操作变快），到严格证明（通过势能函数和 rank 分层），中间有一道需要耐心跨越的鸿沟。对于大多数工程师来说，理解 α(n) ≤ 5 这个结论以及为什么它是上界就够了。但如果你对算法分析有更深的兴趣，摊销分析的分析方法——势能函数法、合计法、记账法——是通向更复杂数据结构分析的通行证。