[理工] 資料結構 Binomial Heap

看板Grad-ProbAsk作者 (優質水瓶男)時間12年前 (2013/10/13 23:50), 編輯推噓0(0推 0噓 6→)
留言6則, 2人參與, 最新討論串1/1
洪逸的筆記寫Binomial Heap 的 Insert 的時間複雜度是 O(1) 但我google查到的是 O(log n) 欸 哪個才是對的阿=.= -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.168.192.42
→
10/14 00:34, , 1F
DS版為O(1)，因為insert X的過程為1. X自己成為一棵
10/14 00:34, 1F
→
10/14 00:36, , 2F
Binomial Heap H2，2.把H2與原本的Binomial Heap merge
10/14 00:36, 2F
→
10/14 00:40, , 3F
步驟2花O(1)的時間。而O(log n)是Algo版本。
10/14 00:40, 3F
→
10/14 00:41, , 4F
洪逸寫的演算法版本也是寫O(1)阿
10/14 00:41, 4F
→
10/14 01:03, , 5F
O(1)為分攤成本，O(log n)為worst case
10/14 01:03, 5F
→
10/14 01:08, , 6F
嗯 謝謝
10/14 01:08, 6F
‣ 更多 ken1325 的文章
文章代碼(AID): #1IMi5OC4 (Grad-ProbAsk)