如何证明Union操作的摊还复杂度（Amortized complexity）为O(log n)？

Great question! It's easy to find general resources on Union-Find amortized complexity, but diving into the specifics of a single Union operation is a nice deep dive. Let's walk through this step by step, focusing on the standard optimized Union-Find implementation with union by rank/size (we'll touch on path compression too, since it's part of the full picture).

Key Background: Optimized Union-Find Setup #

First, let's recap the two critical optimizations that make this complexity achievable:

• Union by Rank/Size: When merging two sets, we always attach the smaller tree (by size or rank—where rank is an upper bound on tree height) to the root of the larger tree. This prevents the tree from degenerating into a chain.
• Path Compression: While this is primarily used in Find operations, it indirectly affects Union (since Union requires two Find calls to locate the roots of the target sets). For our O(log n) proof, we'll start with union by rank alone, then see how path compression tightens this bound.

Proof Using Union by Rank (No Path Compression) #

Let's start with the simpler case where we only use union by rank. We want to show that any sequence of Union operations has amortized O(log n) time per operation.

Step 1: Define the Rank Property #

Each node starts with a rank value of 0. When merging two trees:

• If the roots have different ranks, we attach the tree with the smaller rank to the root of the tree with the larger rank. The rank of the new root stays unchanged.
• If the roots have the same rank, we attach one tree to the other and increment the rank of the new root by 1.

Step 2: Prove the Tree Size Invariant #

A key invariant here is: a tree of rank k has at least 2^k nodes. We can prove this by induction:

• Base case: A rank 0 tree has exactly 1 node (which equals 2^0), so the invariant holds.
• Inductive step: Assume all trees of rank k-1 have at least 2^(k-1) nodes. When we merge two rank k-1 trees, the resulting tree has rank k and size 2^(k-1) + 2^(k-1) = 2^k nodes—satisfying the invariant.

Step 3: Count Node Moves #

Each time a node is moved (i.e., its parent changes during a Union), it's because its current tree is being merged into a larger tree. From the invariant above, every time a node is moved, the size of the tree it belongs to at least doubles.

Since the total number of nodes is n, a node can be moved at most log2(n) times (doubling log2(n) times takes you from 1 node to n nodes).

Step 4: Calculate Amortized Time #

Each Union operation involves two Find calls (to locate roots) plus linking the smaller tree to the larger one. Without path compression, each Find takes O(h) time where h is the tree height—and since h ≤ rank ≤ log2(n), this is O(log n).

For amortized analysis: across all Union operations, the total number of node moves is O(n log n). Dividing this by n operations gives an amortized O(log n) time per Union.

Adding Path Compression #

When we add path compression to Find operations, the amortized bound actually gets tighter (down to the inverse Ackermann function α(n), which grows slower than any logarithmic function). But since α(n) ≤ log n for all practical values of n, the O(log n) bound still holds as a valid upper limit.

Path compression reduces the tree height even further, so nodes are accessed or moved even fewer times than log n. Thus, the amortized time per Union (which relies on Find) remains O(log n) (and in practice, much better).

Summary #

• With union by rank/size alone, each Union operation has amortized O(log n) time because each node can be merged into larger trees at most log n times.
• Adding path compression makes the actual amortized complexity even better, but O(log n) remains a valid and easy-to-prove upper bound.

内容的提问来源于stack exchange，提问作者Göktuğ ÖCAL