社区讨论

并查集复杂度疑问

2024/10/04 06:19学术版参与者 5已保存回复 10

讨论操作

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

当前回复: 10 条
当前快照: 1 份
快照标识符: @m1tv03fz
此快照首次捕获于: 2024/10/04 06:19
此快照最后确认于: 2025/11/04 18:09

按序合并（编号大的往编号小的上合并）+ 路径压缩，复杂度是 $O(n\log n)$ 还是 $O(n\alpha(n))$ ？
朴素 Tarjan 离线 LCA 时间复杂度为什么是 $O(n\alpha(n))$ ？Wiki 没找到解释

回复

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

正在加载回复...