如何进行并集查找二次算法?
在快速查找算法的此实现中,构造函数执行步骤,也是如此。N
union()
讲师说,处理对象上的命令序列太昂贵了,当它一次访问一个数组元素时,联合
怎么能是二次的呢?union
N^2
N
union
N
public class QuickFind
{
private int[] id;
public QuickFind(int N) {
id = new int[N];
for (int i=0; i<N; i++) {
id[i] = i;
}
}
public boolean connected(int p, int q) {
return id[p] == id[q];
}
public void union(int p, int q) {
int pid = id[p];
int qid = id[q];
for (int i=0; i<id.length; i++)
if (id[i] == pid)
id[i] = qid;
}
}