作者AAQ8 ()
看板Grad-ProbAsk
标题[理工] 资料结构 Dijkstra algo时间复杂度
时间Wed Oct 17 20:26:11 2018
https://i.imgur.com/RCJbpwf.jpg
洪逸笔记里的这部分有点不能理解
法二用fib.heap建的时间复杂度
为什麽是写成O(vlogv+E)而不是写O(E)就好
我的想法是
E的最大边数是v(v-1)/2 也就是O(v^2)
如此一来O(v^2)比O(vlogv)来得大
所以时间复杂度是O(v^2)或是O(E)
不知道是哪里想错了
麻烦各位一下
感谢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 39.9.233.117
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1539779173.A.C85.html
1F：推 wilson50101: 不一定每次都到最大边数吧 10/17 20:36
2F：→ wilson50101: 如果边少这样估会太松？ 10/17 20:36
3F：推 BroccolYee: V-1 <= E <= V*(V-1)/2 10/17 20:48
4F：→ BroccolYee: 只写O(E)会不够严谨 10/17 20:48
5F：→ AAQ8: 好奇问一下，法一的时间复杂度可以写O((E+V)logv)吗，如果要 10/17 21:59
6F：→ AAQ8: 够紧的话 10/17 21:59
7F：推 wilson50101: 可以吧 法一本来就O(ElogV+VlogV) 10/18 00:03