3

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

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

定理：从一个空数据结构开始，对 N 个对象的任何 M 个 union 和 find 操作序列都需要 O(N + M lg* N) 时间。

• 证明非常困难。

• 但算法仍然很简单！

但是我还是很好奇迭代对数lg*n是怎么来的。它是如何派生的？有人可以证明它还是以直观的方式解释它？

4

2 回答 2

5

首先，您的问题有一个小错误：仅路径压缩的复杂性仅为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];
    }

按等级联合。

但是，通过秩并集和路径压缩，可以很容易地证明您使用的表达式（比逆阿克曼表达式要容易得多）。证明基于三点：

  1. 在每个叶根路径上，每个节点的等级都在增加。这实际上依赖于按等级联合，顺便说一句，有了它，很容易表现出来。

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

基于2.，可以显示

  1. 秩为r的最大节点数最多为n / 2 r。

证明的其余部分现在是对可能的最坏组织等级的巧妙安排，这仍然表明没有太多是坏的。有关更多详细信息，请参阅有关此的 Wikipedia 条目。

于 2016-09-02T13:19:01.947 回答
1

我记得，证明与将路径压缩的成本摊销到一组搜索有关。浅层搜索很便宜，并且不会产生大量路径压缩的成本；深度搜索对该搜索和路径压缩的成本很高，但路径压缩使后续搜索平均便宜得多。

于 2016-09-02T12:49:46.283 回答