作者FRAXIS (喔喔)
看板Grad-ProbAsk
標題Re: [理工] 106交大資演9
時間Sat Feb 2 13:25:23 2019
※ 引述《q5332159 (chiu)》之銘言：
: http://i.imgur.com/GCwu6aO.jpg
: 想問這題的d～
: algo版是O(log n) DS版是O(1)
: 不知道應該要以哪種作為答案@@
: 還有想問大家遇到問binomial heap或fib heap的時候都會以algo版來回答還是DS版啊？><
: 先謝謝各位～～
: -----
: Sent from JPTT on my HTC_D830x.
對於 Fibonacci Heap 來說，不論 DS 或是 Algo 版的，實作都是一樣，
所以 worst case time/amortized time 都是一樣的。
對於 Binomial Heap 來說，DS 和 Algo 對於 Merge/Insert 的實作不
太一樣。DS 的方法是直接串起來（Lazy Merge），而 Algo 則是每次
Insert/Merge 完都要保證 Binomial Heap 中沒有同 Order 的
Binomial Tree。詳細內容可以看 Wiki。
時間複雜度可以整理如下（Operation 的命名是按照 Algo）。
Binomial (Algo) Lazy-Binomial (DS) Fibonacci
Worst Amortized Worst Amortized Worst Amortized
MakeHeap Θ(1) Θ(1) Θ(1) Θ(1) Θ(1) Θ(1)
Insert Θ(lg n) Θ(1) Θ(1) Θ(1) Θ(1) Θ(1)
Minimum Θ(1) Θ(1) Θ(1) Θ(1) Θ(1) Θ(1)
ExtractMin Θ(lg n) Θ(lg n) Θ(lg n) Θ(lg n) Θ(lg n) Θ(lg n)
Union Θ(lg n) Θ(1) Θ(1) Θ(1) Θ(1) Θ(1)
DecreaseKey Θ(lg n) O(lg n) Θ(lg n) O(lg n) Θ(n) Θ(1)
Delete Θ(lg n) Θ(lg n) Θ(lg n) Θ(lg n) Θ(n) Θ(lg n)
因為 CLRS 舊版（新版的 Binomial Heap 變成習題了）沒有特別分析
amortized time，所以沒辦法在書上直接找到答案。
其中 Minimum 是假設有一個 pointer 指向 minimum element，當進行
其他操作的時候，都必須進行相對應的 update，所以 Minimum 可以在
Θ(1) 完成。Fibonacci Heap 一般都會 maintain 這個 pointer，如果
Binomial Heap 沒有這個 pointer 的話，那 Minimum 的 worst/amortized
就會變成 Θ(lg n)。
而 ExtractMin 課本上一般都是證明 O(lg n)。不過 o(lg n) 是不可能
的，不然就只要靠 Insert/ExtractMin 就可以得到 o(n lg n) 的排序法，
所以不管 worst 或是 amortized 都必須是 Θ(lg n)。
而 Delete 的實作是 DecreaseKey + ExtractMin，所以時間複雜度就
是在 DecreaseKey 和 ExtractMin 挑比較 tight 的 bound 出來。
Fibonacci Heap 的 DecreaseKey 在 worst case 是 Θ(n)，因為
可以藉由一連串 Insert/DecreaseKey/Delete 建構出一個
Fibonacci Tree 是一個 list，且全部的 node 都已經被 mark。
當對 leaf 作 DecreaseKey 時，就必須要把所有 list 上的點都 cut，
會需要 Θ(n) 的時間。
Binomial Heap Insert/Union 的 amortized time 也是 O(1)。
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.420.43
第六小節的第一段最後有提到參考文獻。
Double-ended binomial queues, by C. M. Khoong and H. W. Leong
https://link.springer.com/chapter/10.1007%2F3-540-57568-5_242
至於 Binomial Heap 的 DecreaseKey amortized time 是 O(lg n)，
但是我也找不到有下限的證明，所以沒辦法寫 Θ(lg n)，不過我猜應
該很多人都研究過了，沒有辦法證明出 o(lg n) 的 amortized time，
所以才設計 Fibonacci Heap。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.202.90.47
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1549085126.A.609.html
1F：推 S2067030: 先推，謝謝大大特地回文解釋 02/02 13:40
2F：推 q5332159: 好詳細！太感謝你了！！ 02/02 14:21
3F：→ DLHZ: 為什麼還要分演算法版跟資料結構版 02/02 16:08
4F：推 eigen555: 那請問decrease-key的worst case呢 02/02 17:20
5F：推 eigen555: 我感覺不是O(1)啊 因為他不是問amortize 02/02 17:22
6F：→ S2067030: 樓上你是問bino還是fib，bino是O(logn)，fib是O(1) 02/02 17:32
7F：→ eigen555: 喔喔我是想問Fib 02/02 17:38
8F：→ S2067030: 他可以直接對你想Decrease的值做運算，所以O(1) 02/02 17:41
9F：→ S2067030: 然後因為它採用lazy merge，所以如果你減過頭了破壞結構 02/02 17:42
10F：→ S2067030: 會直接被拉出來，不合併，所以有沒有amor都是O(1) 02/02 17:42
11F：→ S2067030: 還是不懂再說 我在想怎解釋，這部分劉逸上課有特別提醒 02/02 17:43
12F：推 alen0303: 推整理 02/02 21:00
13F：推 eigen555: 感謝 02/03 13:31
※ 編輯: FRAXIS (73.202.90.47), 02/03/2019 14:04:27
14F：推 a28238341a: 推推時間整理很用心感謝! 02/03 17:00
15F：推 skyHuan: 推推 02/03 17:44