一个小问题
  • 板块学术版
  • 楼主Mo默Sh笙
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/9/16 09:36
  • 上次更新2023/11/2 20:18:28
查看原帖
一个小问题
189485
Mo默Sh笙楼主2023/9/16 09:36

优先队列 dijkstra 的复杂度是否可以写成 O(mlog⁡n)O(m\log{n})?

如果去掉重边,mm 最大是 n2n^2,那么 mlog⁡mm\log{m} 可以写成 mlog⁡n2m\log{n^2},也就是 2×mlog⁡n2\times m\log{n},省去常数就是 O(mlog⁡n)O(m\log{n})。

2023/9/16 09:36
加载中...