加权快速连通性算法与路径压缩：时间复杂度分析

Question

加权快速连通性算法与路径压缩：时间复杂度分析

algorithmdata-structurestime-complexityunion-finditerated-logarithm

3

我正在学习用于union/find结构的“带权快速联合与路径压缩”算法。普林斯顿大学的网站详细解释了该算法。（链接）

以下是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次联合和查找操作的任何序列都需要O（N + M lg* N）时间。

• 证明非常困难。

• 但算法仍然很简单！

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

- pjpj

1

如果某个证明被认为很难，那么它一定存在，并且某人已经证明了它。 - Scott Hunter

2个回答

1

据我回忆，证明与在一组搜索中分摊路径压缩成本有关。浅层搜索很便宜，不会产生太多路径压缩的成本；深度搜索对于该搜索和路径压缩的成本代价很高，但路径压缩使得后续搜索平均来说更加便宜。

- Scott Hunter

我理解这些，但是 lg*n 是什么意思？ - pjpj

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ami Tavory · Accepted Answer

首先，您的问题略有错误：仅具有路径压缩的复杂度为O(m log(n))（没有迭代对数）。例如，请参见练习21-4.4 in 算法导论。实际上，您的块

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

使用秩合并和路径压缩，可以很容易地证明你所使用的表达式（比反阿克曼函数更容易）。证明基于以下三个要点：

在每个叶子根路径上，每个节点的秩都在增加。顺便说一下，这实际上依赖于秩合并，使用它可以很容易地展示。
如果树的根具有秩r，那么该树至少有2^r个节点。这可以通过归纳来展示。

基于第二点，可以展示

秩为r的节点的最大数量不超过n / 2^r。

现在，剩余的部分通过巧妙地安排秩的最坏可能方式来跟踪证明，尽管排列方式很糟糕，但仍然显示出坏的节点不会太多。有关更多详细信息，请参见此 Wikipedia 条目。