为什么Dijkstra复杂度mlogn而不是nlogn+m
  • 板块学术版
  • 楼主Xy_top
  • 当前回复25
  • 已保存回复25
  • 发布时间2023/9/6 19:59
  • 上次更新2023/11/2 22:32:16
查看原帖
为什么Dijkstra复杂度mlogn而不是nlogn+m
637796
Xy_top楼主2023/9/6 19:59

rtrt,每个点只会被松弛一次,每个点取出后会遍历所有与它相邻的节点,每个点这一部分的时间复杂度加起来是 O(m)O(m),而优先队列里最多会有 nn 个元素,所以它的复杂度难道不是 O(nlog⁡n+m)O(n\log n+m)

2023/9/6 19:59
加载中...