@[only_once](/user/1328928) M是边数，N是点数，应该是$O(Mlogn)$
by 1217Eirc @ 2024-09-20 13:11:15
不对 吧O(n) 优化成 O(logn) 怎么也是正向优化吧 （建议学习什么是堆）
by lhz2022 @ 2024-09-20 13:11:43
@[lhz2022](/user/822439) 指每次更新
by lhz2022 @ 2024-09-20 13:12:19
@[only_once](/user/1328928) 捞
by lhz2022 @ 2024-09-20 13:13:08
确实是这样的，完全图上跑普通 dijkstra 是 $O(n^2)$，带上堆优化是 $O(m\log n)$，也就是 $O(n^2\log n)$。其中 $n$ 是点数，$m$ 是边数。
by zhujiangyuan @ 2024-09-20 13:15:57
ok,谢谢大佬们，此贴结
by only_once @ 2024-09-20 13:17:16
@[only_once](/user/1328928)
完全图$m$约等于$n^{2}$，
朴素dijkstra为$O(n^{2})$，而堆优化dijkstra
手写堆是$O(mlogn)$,STL是$O(mlogm)$，此时比朴素慢
（不过$log(n^{2})=2log(n)$，手写和STL差不多）
by paradise520 @ 2024-09-20 13:20:06