[理工] 104台大资演 pureblue1234 PTT批踢踢实业坊

楼主: pureblue1234 (1234) 2018-01-23 15:15:22

https://i.imgur.com/iVud8yq.jpg
请问第二题为什么是O(ElogV)而不是直接写O(V^2)

作者: a28238341a (小蜗) 2018-01-23 15:56:00

资料结构不一样

楼主: pureblue1234 (1234) 2018-01-23 16:07:00

请问从哪看出资料结构不同，不是只跟你说loser tree,它的树叶放最小编长吗?为什么是Elogv

作者: djmez 2018-01-23 16:17:00

第一题硬干才会这么大然后使用非fib (Decrease-key成本不为1)的高度平衡树做的话成本都是O(VlogV+ElogV)

作者: a28238341a (小蜗) 2018-01-23 16:21:00

我是用推的啦因为1.3题是V^2跟Fib Heap的ElogV打错了 VlogV+E

作者: djmez 2018-01-23 16:23:00

把P.135看一下然后找各结构的删除最小、decrease-key带入就知道了

作者: Dora5566 (咩休干某) 2018-01-27 17:07:00

prim可以用费波堆积？!

继续阅读