[問題] 有關binomial heap的find min的複雜度
看板Prob_Solve (計算數學 Problem Solving)作者JinSha ( )時間7年前 (2017/11/30 00:13)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/2 (看更多)
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://www.ptt.cc/bbs/Prob_Solve/M.1511971998.A.B8C.html
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
