堆优dij时间复杂度是多少?
  • 板块学术版
  • 楼主Mr_Water
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/9/18 08:36
  • 上次更新2023/10/27 11:02:44
查看原帖
堆优dij时间复杂度是多少?
573641
Mr_Water楼主2022/9/18 08:36

题目:对一个 nn 个顶点,mm 条边的带正权有向简单图使用 Dijkstra 算法计算 单源最短路时,如果再使用一个可以在 Θ(logn)\Theta(\log n) 时间复杂度内查询堆内最 小值、在 Θ(n)\Theta(\sqrt{n}) 时间复杂度内合并两个堆、在 Θ(1)\Theta(1) 时间复杂度内将堆内一个元素变小、在 Θ(logn)\Theta(\log n) 时间复杂度内弹出堆内最小值的堆优化 Dijkstra 算法,则整个 Dijkstra 算法的时间复杂度为 ( O(m+nlogn)O(m + n \log n) )

书上写的是 O((m+n)logn)O((m+n) \log n) ,这道题目的堆有什么特殊之处吗?

2022/9/18 08:36
加载中...