并查集复杂度

[giscus[bot]]

并查集复杂度

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

https://oiwiki.com/ds/dsu-complexity/

[gsc0618china]

tql

[yz4004]

https://link.springer.com/chapter/10.1007/11523468_7
似乎是参考这篇， 可以结合着看

[MTDickens]

Tim Roughgarden 有详细讲，可以参考他的视频：

1. Hopcroft-Ullman 的分析（复杂度上限 $O(\log* n)$ ）：
   1. Hopcroft-Ullman 的分析-上
   2. Hopcroft-Ullman 的分析-下
2. Tarjan 的分析（复杂度上限 $O(\alpha (n))$）：
   1. 什么是 Ackermann 函数
   2. Tarjan 的分析-上
   3. Tarjan 的分析-下

[MTDickens]

注：$O(\log *n)$ 就是迭代对数函数

[MTDickens]

$\alpha(n)$ 就是反阿克曼函数。

另，如果不是老手，不要轻易硬啃这个复杂度分析。还是要听课。

Tim Roughgarden 除了讲这个算法以外，还有一整套的算法课程-Coursera: Algorithm Specialization。如果有还没有系统上算法课程的朋友，推荐一听。

[ShawxingKwok]

推荐看《算法导论》，先学摊还分析中的势能，然后耐心点看并查集的最后一节，关键是耐心。