PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 有關binomial heap的find min的複雜度

看板Prob_Solve (計算數學 Problem Solving)作者 (...)時間7年前 (2017/11/30 05:11), 7年前編輯推噓6(6推 0噓 24→)
留言30則, 6人參與, 8年前最新討論串2/2 (看更多)
※ 引述《JinSha ( )》之銘言： : 所以若是遇到問的問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) https://en.wikipedia.org/wiki/Binomial_heap#Find_minimum To find the minimum element of the heap, find the minimum among the roots of the binomial trees. This can again be done easily in O(log n) time, as there are just O(log n) trees and hence roots to examine. By using a pointer to the binomial tree that contains the minimum element, the time for this operation can be reduced to O(1). The pointer must be updated when performing any operation other than Find minimum. This can be done in O(log n) without raising the running time of any operation. 也就是說，原本是 O(log n)，但是可以取巧改進到 O(1)。 題外話： 實務上沒有人使用 binomial heap，甚至實務上沒有人使用任何一種 heap。 同樣的事情可以用 binary search tree 做到。(除了合併操作)(感謝LPH66指正) 教科書會寫 binomial heap，是因為作者覺得這很有特色，具有一咪咪理論上的價值。 教授上課會教 binomial heap，是因為臺灣教授的水平，僅止於複誦教科書。 研究所考試會考 binomial heap，是因為教授要貫徹上意，達成我國愚民教育的方針。 至於正確答案應該要填 O(1) 還是 O(log n)，其實是教授說了算，他們爽就好。 反正現實世界沒有人在用。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.167.24.34 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1511989884.A.E17.html ※ 編輯: DJWS (118.167.24.34), 11/30/2017 05:17:15
推
11/30 09:12, 7年前 , 1F
我不同意 BST 可以取代 heap; 就拿這題的 binomial heap
11/30 09:12, 1F
→
11/30 09:12, 7年前 , 2F
來說, 它提供了 O(log n) 合併兩個 heap 的操作
11/30 09:12, 2F
→
11/30 09:13, 7年前 , 3F
這是 BST 無法達成的
11/30 09:13, 3F
→
11/30 09:16, 7年前 , 4F
另外實務上沒人用這句話我想打個問號
11/30 09:16, 4F
→
11/30 09:17, 7年前 , 5F
priority queue 這種資料結構就我所知底層都是 heap
11/30 09:17, 5F
→
11/30 09:18, 7年前 , 6F
甚至 C++ STL 有 make_heap push_heap pop_heap sort_heap
11/30 09:18, 6F
→
11/30 09:18, 7年前 , 7F
這都是標準的 binary heap 的操作
11/30 09:18, 7F
推
11/30 12:26, 7年前 , 8F
不過的確就算以學習理論的角度而言, binomial跟Fibonacci
11/30 12:26, 8F
→
11/30 12:27, 7年前 , 9F
heaps為了達成deterministic而使證明複雜的代價太大了.
11/30 12:27, 9F
→
11/30 12:28, 7年前 , 10F
稍微引入一點隨機性就可以教treap了, 更別說它跟quicksort
11/30 12:28, 10F
→
11/30 12:28, 7年前 , 11F
的緊密關聯...
11/30 12:28, 11F
→
11/30 18:14, 7年前 , 12F
@LPH66 合併兩個heap，現實世界哪裡在使用，請你舉個實例
11/30 18:14, 12F
→
11/30 18:29, 7年前 , 13F
有一種 bst 叫做 splay tree，合併操作均攤 O(log n)
11/30 18:29, 13F
^^^^^^^^ 錯了 當我沒說 XD
推
11/30 23:22, 7年前 , 14F
binary heap 常數會比 bst 小吧
11/30 23:22, 14F
→
11/30 23:23, 7年前 , 15F
我覺得這樣就算有實用價值了
11/30 23:23, 15F
→
12/01 04:31, 7年前 , 16F
樓上可能不知道"常數"是中國競賽選手自創詞彙 工程師討論
12/01 04:31, 16F
→
12/01 04:31, 7年前 , 17F
這種事情時所用的詞彙叫做benchmark
12/01 04:31, 17F
→
12/01 04:38, 7年前 , 18F
另外 除了程式語言內建的binary heap以外 真實世界哪裡在
12/01 04:38, 18F
→
12/01 04:38, 7年前 , 19F
使用binary heap 歡迎大家舉個實例
12/01 04:38, 19F
※ 編輯: DJWS (118.167.31.208), 12/01/2017 06:03:51
推
12/01 10:05, 7年前 , 20F
constant factor 這詞演算法課本也有提到
12/01 10:05, 20F
我記下來了 謝謝
→
12/01 10:09, 7年前 , 21F
我有找到 splay tree union 均攤 O(log n) 的論文耶
12/01 10:09, 21F
→
12/01 10:10, 7年前 , 22F
12/01 10:10, 22F
→
12/01 17:40, 7年前 , 23F
binomial heap 總共 O(log n) splay tree 總共 O(n log n)
12/01 17:40, 23F
→
12/01 17:42, 7年前 , 24F
雖然均攤 O(log n)，但是根本就沒有比較意義，所以當我沒說
12/01 17:42, 24F
※ 編輯: DJWS (220.137.8.154), 12/01/2017 17:43:22
推
12/09 00:35, 7年前 , 25F
binary search tree跟heap寫起來難度差那麼多...
12/09 00:35, 25F
→
12/09 07:33, 7年前 , 26F
compiler = 100 bst = 2 heap = 1 似乎是比較難沒錯啦
12/09 07:33, 26F
推
01/02 23:35, 8年前 , 27F
我做的是eda中physical design裡面的p&r tool
01/02 23:35, 27F
→
01/02 23:36, 8年前 , 28F
我們的code就有heap 而且是自己寫的
01/02 23:36, 28F
→
01/12 15:04, 8年前 , 29F
那請教你，輸入資料數量多大？
01/12 15:04, 29F
→
01/12 15:07, 8年前 , 30F
還有就是，是什麼任務需要即時得知最小值？
01/12 15:07, 30F
‣ 更多 DJWS 的文章
文章代碼(AID): #1Q7o9yuN (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 DJWS 的文章
文章代碼(AID): #1Q7o9yuN (Prob_Solve)