作者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/cn.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