作者pureblue1234 (1234)
看板Grad-ProbAsk
标题[理工] 104台大资演
时间Tue Jan 23 15:15:22 2018
https://i.imgur.com/iVud8yq.jpg
请问第二题为什麽是O(ElogV)而不是直接写O(V^2)
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 120.101.11.50
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1516691725.A.86C.html
1F：推 a28238341a: 资料结构不一样 01/23 15:56
2F：→ pureblue1234: 请问从哪看出资料结构不同，不是只跟你说loser tree 01/23 16:07
3F：→ pureblue1234: ,它的树叶放最小编长吗?为什麽是Elogv 01/23 16:07
4F：推 djmez: 第一题硬干才会这麽大 01/23 16:17
5F：推 djmez: 然後使用非fib (Decrease-key成本不为1)的高度平衡树做的 01/23 16:19
6F：→ djmez: 话成本都是O(VlogV+ElogV) 01/23 16:19
7F：→ a28238341a: 我是用推的啦 因为1.3题是V^2跟Fib Heap的ElogV 01/23 16:21
8F：→ a28238341a: 打错了 VlogV+E 01/23 16:22
9F：→ djmez: 把P.135看一下 然後找各结构的删除最小、decrease-key带入 01/23 16:23
10F：→ djmez: 就知道了 01/23 16:23
11F：推 Dora5566: prim可以用费波堆积？! 01/27 17:07