关于并查集只用路径压缩加随机合并时间复杂度
  • 板块学术版
  • 楼主x383494
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/7/8 13:22
  • 上次更新2023/11/3 11:04:01
查看原帖
关于并查集只用路径压缩加随机合并时间复杂度
747335
x383494楼主2023/7/8 13:22

RT,OI Wiki 上说,

在姚期智的论文 [2] 中,证明了不使用启发式合并、只使用路径压缩,在平均情况下,时间复杂度依然是 O(mα(m,n))O (m\alpha(m,n)) 。

那我每次合并时随机合并一点到另一点是否可以使它复杂度不退化

2023/7/8 13:22
加载中...