关于最小生成树
  • 板块学术版
  • 楼主zhangbo1000
  • 当前回复16
  • 已保存回复16
  • 发布时间2024/9/25 13:28
  • 上次更新2024/9/25 18:34:37
查看原帖
关于最小生成树
760291
zhangbo1000楼主2024/9/25 13:28

rt,当边权为整数时,如果采用基数排序等 Θ(n)\Theta(n) 的排序方式对边排序并使用按秩合并加路径压缩的并查集,Kruskal 算法的时间复杂度应该能到 Θ(n)\Theta(n)(或者更准确的说,Θ(nα(n))\Theta(n\alpha(n))) 吧,但是我从来没有见过人这么写,是上述方法有什么缺陷吗?

2024/9/25 13:28
加载中...