作者JinSha ( )
看板Prob_Solve
标题[问题] 有关binomial heap的find min的复杂度
时间Thu Nov 30 00:13:12 2017
http://www.geeksforgeeks.org/binomial-heap-2/
2) getMin(H): A simple way to getMin() is to traverse the list of root of
Binomial Trees and return the minimum key. This implementation requires
O(Logn) time. It can be optimized to O(1) by maintaining a pointer to minimum
key root.
----
所以若是遇到问的问binomial heap的find min的复杂度时，
有的地方会说O(log n)，有的地方会说O(1)
比方说
https://en.wikipedia.org/wiki/Binomial_heap#cite_note-amortized-9
http://www.growingwiththeweb.com/data-structures/binomial-heap/overview/
这两的地方是说O(log n)
也有的地方
http://www.geeksforgeeks.org/leftist-tree-leftist-heap/
Get Min: O(1) [same as both Binary and Binomial]
是说O(1)
那麽若是遇到选择题，尤其是复选题时
https://tinyurl.com/y7wqazrf
如台大104年资料结构(B)第12题的选项（A）
因为没有办法如问答题可以解释，那麽要以O(log n)还是O(1)来作答呢？
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.198.177.248
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1511971998.A.B8C.html