gpt4 book ai didi

java - 带路径压缩的加权快速联合

转载 作者:行者123 更新时间:2023-12-01 14:10:08 25 4
gpt4 key购买 nike

根据普林斯顿书站的说法,带有路径压缩的加权快速联合将 10^9 对象上的 10^9 联合操作的时间从一年减少到约 6 秒。这个数字是如何得出的?当我以 10^8 次操作运行以下代码时,运行时间为 61 秒。

public class MainWQUPC{
public static void main(String[] args){
int p, q;
Scanner s = new Scanner(System.in);

long N = s.nextLong();

WQUPC uf = new WQUPC((int) N);

for(int x = 0; x < N; x++){
p = (int) (Math.random() * N);
q = (int) (Math.random() * N);

if(!uf.connected(p, q))
uf.union(p, q);
}
}
}

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];
}
}
}

最佳答案

您无法直接进行比较,因为运行时间取决于许多不同的因素,在本例中主要取决于 CPU 性能。

假设一年平均约为 31556952 秒 (60*60*24*365.2425)使用路径压缩大约需要 6 秒

这意味着带有路径压缩的快速联合大约是比没有快 5259492 (31556952/6) 倍。

因此给出的数字只是表明,当您“只是”稍微改进算法时,性能提升是多么令人难以置信。

关于java - 带路径压缩的加权快速联合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18580683/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com