社区讨论

求问路径压缩并查集复杂度（玄关）

BBestart
学术版参与者 9已保存回复 21

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
21 条
当前快照
1 份
快照标识符
@mjpgx6to
此快照首次捕获于
2025/12/28 16:29
2 个月前
此快照最后确认于
2025/12/31 23:55
2 个月前
查看原帖
感觉纯路径压缩并查集的复杂度是 O(n)O(n) 的，不带 log⁡n\log n 吧？
对于时间复杂度-势能分析浅谈中做出的对比，我不太认同，原因有以下几点（看不懂他的势能分析，只对 Hack 进行质疑）：
  1. 爆栈只能说明栈空间开小了（即树高偏大），而不能说明时间复杂度错误。
  2. 多次运行可能是常数导致的，并不能说明具体问题，而且数据范围偏小，难以断定。
  3. 真正正确的做法应该是增大 n,mn , m 的范围，而不是小范围反复跑。
使用作者 木木！提供的 Hack 代码得到数据，数据范围 1≤n≤106,1≤m≤2×1061 \le n \le 10 ^ 6 , 1 \le m \le 2 \times 10 ^ 6，造出题目并查集测试。
吐槽一下，怎么代码的输出结果都是 Y。
结果如下：
代码总运行时间
作者提供的纯路径压缩的代码 304ms \text{ 304ms }
作者提供的路径压缩和按秩合并的代码 282ms \text{ 282ms }
本人自己写的纯路径压缩的代码 687ms \text{ 687ms }
本人自己写的路径压缩和按秩合并的代码 664ms \text{ 664ms }
本人自己写的路径压缩和启发式合并的代码 657ms \text{ 657ms }
可以看到只存在常数级优化，并不能直接让复杂度少掉 log⁡\log，不然差值不会在  30ms \text{ 30ms } 以内。
另附机房电脑运行 1≤n≤107,1≤m≤2×1071 \le n \le 10 ^ 7 , 1 \le m \le 2 \times 10 ^ 7 的结果（文件过大，无法上传至洛谷）：
代码总运行时间
作者提供的纯路径压缩的代码 5581ms \text{ 5581ms }
作者提供的路径压缩和按秩合并的代码 4.849ms \text{ 4.849ms }
本人自己写的纯路径压缩的代码 3736ms \text{ 3736ms }
本人自己写的路径压缩和按秩合并的代码 3901ms \text{ 3901ms }
本人自己写的路径压缩和启发式合并的代码 3751ms \text{ 3751ms }
电脑配置：学校机房， 10th Gen Intel(R) Core(TM)i5 \text{ 10th Gen Intel(R) Core(TM)i5 }，内存  16 GB \text{ 16 GB }。
所以路径压缩的复杂度到底是多少？如果确实带 log⁡n\log n，那么怎么 Hack？
求证明复杂度/Hack，轻喷。

回复

共 21 条回复，欢迎继续交流。

正在加载回复...