带路径压缩算法的加权快速联合：时间复杂度分析

Question

我正在学习"Weighted quick-union with path compression" union/find 结构的算法。 Princeton edu site 详细解释了算法。这是 Java:

中的实现

public class WQUPC {
  private int[] id;
  private int[] sz;
  public WQUPC(int N) {
    id = new int[N];
    sz = new int[N];
    for (int i = 0; i < N; i++) {
      id[i] = i;
      sz[i] = 1;
    }
  }

  int root(int i) {
    while (i != id[i]) {
      id[i] = id[id[i]];
      i = id[i];
    }
    return i;
  }

  boolean connected(int p, int q) { return root(p) == root(q); }

  void union(int p, int q) {
    int i = root(p);
    int j = root(q);
    if (sz[i] < sz[j]) {
      id[i] = j;
      sz[j] += sz[i];
    } else {
      id[j] = i;
      sz[i] += sz[j];
    }
  }
}

但是就像网站提到的性能一样：

Theorem: Starting from an empty data structure, any sequence of M union and find operations on N objects takes O(N + M lg* N) time.

• Proof is very difficult.

• But the algorithm is still simple!

不过我还是很好奇迭代对数lg*n是怎么来的。它是如何推导出来的？有人可以证明它或者用直观的方式解释它吗？

Answer 1

我记得，证明与分摊一组搜索的路径压缩成本有关。浅搜索很便宜，不会产生太多路径压缩的成本；对于该搜索和路径压缩，深度搜索的成本很高，但路径压缩使后续搜索平均成本更低。

Answer 2

首先，您的问题有一个小错误：仅路径压缩的复杂性仅为 O(m log(n))（没有迭代日志）。例如，参见 Introduction To Algorithms 中的练习 21-4.4。事实上，你阻止了

    if (sz[i] < sz[j]) {
      id[i] = j;
      sz[j] += sz[i];
    } else {
      id[j] = i;
      sz[i] += sz[j];
    }

按等级合并。

但是，通过按等级合并和路径压缩，可以轻松证明您使用的表达式（比逆阿克曼表达式容易得多）。证明基于三点：

在每条叶根路径上，每个节点的秩都是递增的。这实际上依赖于 union by rank，顺便说一句，有了它，很容易证明。
如果一棵树的根有等级r，这棵树至少有2^r 个节点。这可以通过归纳来证明。

在2.的基础上，可以显示

等级为r的最大节点数最多为n / 2^r .

接下来的证明是最糟糕的排列方式的巧妙安排，这仍然表明没有太多是坏的。有关详细信息，请参阅 Wikipedia entry on this.

带路径压缩算法的加权快速联合：时间复杂度分析

Weighted quick-union with path compression algorithm: time complexity analysis

algorithm

time-complexity

data-structures

union-find

iterated-logarithm