关于并查集在数据较小时路径压缩的性能的疑问
  • 板块学术版
  • 楼主b__b
  • 当前回复7
  • 已保存回复7
  • 发布时间2025/8/5 10:18
  • 上次更新2025/8/5 15:11:37
查看原帖
关于并查集在数据较小时路径压缩的性能的疑问
1121063
b__b楼主2025/8/5 10:18

rt,先给出一个我自己写的路径压缩的并查集:

int find(int x) {
    return se[x] == x ? x : (se[x] = find(se[x]));
}

没用路径压缩:

int find(int x) {
    return se[x] == x ? x : find(se[x]);
}

第二份代码可以进行尾调用优化,但是第一份应该不可以?

如果是的话,那么当数据较小,路径压缩带来的优化不明显时,会不会出现不用路径压缩反而更快的现象?

本人比较笨,想不清楚,所以发到讨论区问问各路大神 qwq

2025/8/5 10:18
加载中...