个人关于堆优dijkstra时间复杂度问题的分析，请各位
  • 板块学术版
  • 楼主AffineRing
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/7/23 19:53
  • 上次更新2023/11/4 13:32:02
查看原帖
个人关于堆优dijkstra时间复杂度问题的分析，请各位
399250
AffineRing楼主2021/7/23 19:53
  1. 使用堆优化的dijkstra。每条边都经过了松弛操作；每个点都需要被取出和删除一次。每个上述操作都是 log⁡\log 的。
  2. 使用一般的手写堆优化的时间复杂度是 O((n+m)log⁡n)O((n+m)\log n)，而优先队列是 O((n+m)log⁡m)O((n+m)\log m)。因为优先队列是没有删除的所以堆里的元素数量没有更少。
  3. 如果出现错误请各位指正。
2021/7/23 19:53