[理工] 资结 Fibonacci heap

楼主: gary19941208   2016-08-20 12:21:34
http://i.imgur.com/BlULJjM.jpg
答案有给C选项
Fibonacci heap的insert和Binomial heap的insert一样
如果是资料结构版本的话是O(1)
算法版本的话在merge的地方是O(log n),但是如果原本没有高度1的binomial tree,
那insert时做的merge就不会有高度相同需要合并,所以是O(1),洪逸上课时说分摊成本
是O(1),这样的话答案是错了吗?
另外想请问分摊成本O(1)怎么知道的,两次插入不就会有一次merge需要O(log n)这样O(1
)和O(log n)的次数好像差不多?
谢谢!
作者: krusnoopy (push)   2016-08-20 13:34:00
fib heap是只有在delete min才需要合并 插入应该不用我查了,的确只要在删除才要合并所以O(1)
楼主: gary19941208   2016-08-20 19:31:00
感谢!
作者: FRAXIS (喔喔)   2016-08-20 21:45:00
插入 amortized O(1) 是因为 O(lg n) 的情况不常出现
作者: krusnoopy (push)   2016-08-20 21:52:00
sorry我刚刚讲的是资结版..
楼主: gary19941208   2016-08-20 22:55:00
我看算法的原文书他插入也没有合并欸....
作者: krusnoopy (push)   2016-08-20 23:15:00
哈哈我回家之后也看到了
楼主: gary19941208   2016-08-21 08:55:00
感觉算法的和资结的是一样的...?算法也是有minpointer
作者: krusnoopy (push)   2016-08-21 23:31:00
那应该只有binomial heap不一样,资结版才可以把fib heap定义在binomail heap上面

Links booklink

Contact Us: admin [ a t ] ucptt.com