不好意思，这篇藉著前人的文来问第二小题，第二小题我看网友的答案是O(V^2)，但我自
己后来推了几次，到现在还是觉得Loser Tree可以用来当Priority Queue(V个Run，E个Da
ta，建树：O(V)，找最小找到结束：O(ElogV))
这个样子的话Extract-min(Q)就可以由一般的搜寻V*V降到V*logV，DcreaseKey总共则是E
logV(如果演算中不用任何DecreaseKey，我认为是O((V-1)*2E)=O(VE)，意即每次跑新的
点要更新cost阵列时都要全部2E条边跑一遍)
以上是小弟想法，还请教各位演算神人的指导，感谢！
※ 引述《cschenptt (chen)》之铭言：
: 题目：
: https://i.imgur.com/jZlEzBr.png
: 我的想法：
: https://i.imgur.com/JDGuqyF.jpg
: 谢谢大家

Array decrease key 也是O(1)

1. E=O(V^1.5) => O(V^2.5) ?2.O(VlgV+ElgV) => O(VlgV+V^1.5lgV) => O(V^1.5lgV)我的想法也是这样

第一题因为 findmin 是 O(n), decreasekey 是 O(1)所以复杂度应该是 O(|V|*n + |E| * 1) = O(nV) = (V^2)

Decrease Key 用Fib.heap才是O(1)?