我正在学习用于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是如何推导出来的?有人能证明它或以直观的方式解释吗?