https://i.imgur.com/iVud8yq.jpg
请问第二题为什么是O(ElogV)而不是直接写O(V^2)
作者: a28238341a (小蜗) 2018-01-23 15:56: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带入就知道了