Re: [理工] 106交大資演9
: 想問這題的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://www.ptt.cc/bbs/Grad-ProbAsk/M.1549085126.A.609.html
推
02/02 13:40,
5年前
, 1F
02/02 13:40, 1F
推
02/02 14:21,
5年前
, 2F
02/02 14:21, 2F
→
02/02 16:08,
5年前
, 3F
02/02 16:08, 3F
推
02/02 17:20,
5年前
, 4F
02/02 17:20, 4F
推
02/02 17:22,
5年前
, 5F
02/02 17:22, 5F
→
02/02 17:32,
5年前
, 6F
02/02 17:32, 6F
→
02/02 17:38,
5年前
, 7F
02/02 17:38, 7F
→
02/02 17:41,
5年前
, 8F
02/02 17:41, 8F
→
02/02 17:42,
5年前
, 9F
02/02 17:42, 9F
→
02/02 17:42,
5年前
, 10F
02/02 17:42, 10F
→
02/02 17:43,
5年前
, 11F
02/02 17:43, 11F
推
02/02 21:00,
5年前
, 12F
02/02 21:00, 12F
推
02/03 13:31,
5年前
, 13F
02/03 13:31, 13F
※ 編輯: FRAXIS (73.202.90.47), 02/03/2019 14:04:27
推
02/03 17:00,
5年前
, 14F
02/03 17:00, 14F
推
02/03 17:44,
5年前
, 15F
02/03 17:44, 15F
討論串 (同標題文章)
