堆优化的dijkstra
大佬们请问为什么时间复杂度为什么不是nlogn呀？
我理解的是每轮循环确定起点到一个点的最短距离，所以总共有n轮循环，所以应该是n*logn呀
猪啊猪
,
2021-05-02 22:49:32
,
所有人可见
,
阅读 978
堆优化的dijkstra
大佬们请问为什么时间复杂度为什么不是nlogn呀？
我理解的是每轮循环确定起点到一个点的最短距离，所以总共有n轮循环，所以应该是n*logn呀
最坏情况下是m次decrease key 和n次pop.用二叉堆等实现是$O((m+n)\log n)$,用fib堆可以做到$O(m+n\log n)$
如果用的是不支持decrease key 的堆（如
std::priority_queue）和懒惰删除，复杂度是$O((m+n)\log m)$$n$表示节点数，$m$表示边数
谢谢xdhh~
堆插入一个元素的时间复杂度是$log(N)$，$N$是堆的大小，堆优化中的dijkstra算法中的堆的大小就是边的数量，一共有$n$个节点，所以有$n$次迭代，每次迭代都有可能插入元素到堆里，插入的复杂度为$log(m)$
哦哦哦谢谢xd