作者leviliang (levi)
看板Grad-ProbAsk
标题Re: [理工] 104台大资演 Prim's
时间Mon Jan 7 20:23:18 2019
不好意思，这篇藉着前人的文来问第二小题，第二小题我看网友的答案是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
: 谢谢大家
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 115.82.199.196
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1546863801.A.682.html
1F：推 htc018220: 1. E=O(V^1.5) => O(V^2.5) ? 01/08 19:08
2F：推 htc018220: 2.O(VlgV+ElgV) => O(VlgV+V^1.5lgV) => O(V^1.5lgV) 01/08 19:11
3F：→ htc018220: 我的想法也是这样 01/08 19:11
4F：→ FRAXIS: 第一题因为 findmin 是 O(n), decreasekey 是 O(1) 01/08 23:41
5F：→ FRAXIS: 所以复杂度应该是 O(|V|*n + |E| * 1) = O(nV) = (V^2) 01/08 23:42
6F：推 htc018220: Decrease Key 用Fib.heap才是O(1)? 01/09 09:48
7F：→ z3588191: Array decrease key 也是O(1) 01/10 20:28