[理工] 资料结构 Dijkstra algo时间复杂度 AAQ8 PTT批踢踢实业坊

[理工] 资料结构 Dijkstra algo时间复杂度

楼主: AAQ8 (不要就是要) 2018-10-17 20:26:11

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)
不知道是哪里想错了
麻烦各位一下
感谢

作者: wilson50101 (我觉得我还不错啊) 2018-10-17 20:36:00

不一定每次都到最大边数吧如果边少这样估会太松？

作者: BroccolYee (花椰菜) 2018-10-17 20:48:00

V-1 <= E <= V*(V-1)/2只写O(E)会不够严谨

楼主: AAQ8 (不要就是要) 2018-10-17 21:59:00

好奇问一下，法一的时间复杂度可以写O((E+V)logv)吗，如果要够紧的话

作者: wilson50101 (我觉得我还不错啊) 2018-10-18 00:03:00

可以吧法一本来就O(ElogV+VlogV)

继续阅读

[理工] 算法 convex hull 极点wilson50101 [理工] 线代古典伴随矩阵AAQ8 [理工] 线代第二章AAQ8 [理工] 计组下册 P.307 Utilizationjojoboy0115 [理工] 计组下p.298 Disk average timeghost1025 [理工] 离散2-33 （c)!Aa841018 [商管] 谁能存取台湾经济新报光盘资料? 优厚报酬yuwenche [理工] 算法DAG求最短路径wilson50101 [理工] 算法递回hl654ck6 [理工] 算法MST第35题wilson50101