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

Question

我正在学习联合/查找结构的“加权快速联合与路径压缩”算法。普林斯顿edu网站详细解释了该算法。这是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];
    }
  }
}

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

定理：从空数据结构开始，任何 M 并集序列和对 N 个对象的查找操作都需要 O（N M lg* N） 时间。

证明非常困难。

但是算法仍然很简单！

但我仍然很好奇迭代对数lg*n是如何产生的。它是如何推导出来的？有人可以证明它或只是以直观的方式解释它吗？

Answer 1

我记得，证明是将路径压缩的成本分摊到一组搜索上。浅搜索很便宜，而且不会产生太多路径压缩的成本；深度搜索的搜索和路径压缩成本很高，但是路径压缩使后续搜索平均便宜得多。

Answer 2

首先，您的问题有一个小错误：仅路径压缩的复杂性仅为O（m log（n））（没有迭代日志）。例如，请参阅算法简介中的练习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和path compression，可以很容易地证明您使用的表达式(比逆阿克曼表达式容易得多)。证据基于三点:

>

在每个叶根路径上，每个节点的排名都在增加。这实际上依赖于按等级合并，顺便说一句，并且，有了它，它很容易显示。

如果树的根具有秩r，则树至少有2个^r节点。这可以通过归纳来证明。

基于2.，可以显示

接下来的证据是对最糟糕的等级组织方式的巧妙安排，这仍然表明没有太多的人是坏的。欲了解更多细节，请参见维基百科关于此的条目。