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)的次数好像差不多?
谢谢!