看板 Prob_Solve 關於我們 聯絡資訊
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