作者q5332159 (chiu)
看板Grad-ProbAsk
標題[理工] 106交大資演9
時間Sat Feb 2 11:49:41 2019
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.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.12.160.203
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1549079384.A.C17.html
※ 編輯: q5332159 (39.12.160.203), 02/02/2019 11:51:38
1F：推 eric131204: 問一下為何algo版是Logn 不是lazy merge嗎 02/02 11:57
2F：→ q5332159: lazy merge 不是DS版嗎 02/02 11:59
3F：→ q5332159: 還是只要是fib就是以DS版為基礎啊？><我疑惑好久了 02/02 12:00
4F：→ q5332159: 可是我的筆記decrease key的部分又有考慮兩版…@@ 02/02 12:02
6F：推 eric131204: 所以algo版不能lazy merge所以跟binomial heap的merge 02/02 12:02
7F：→ eric131204: 一樣？ 02/02 12:02
8F：推 plsmaop: CLRS p518，用amortized cost O(lgn)，我覺得這種定義問 02/02 12:08
9F：→ plsmaop: 題老師應該比較喜歡用CLRS的定義 02/02 12:08
10F：推 FRAXIS: Fib 的 union 應該都是直接串起來.. 所以一定是O(1) 吧 02/02 12:16
11F：→ FRAXIS: Binomial Heap 的 Merge 才會有 worst case O(lg n) 02/02 12:17
12F：→ FRAXIS: Amortized cost O(1) 的差別 02/02 12:17
13F：推 plsmaop: 我看成b, sorry，CLRS p512裡說union是amortized O(1)， 02/02 12:27
14F：→ plsmaop: 用potential method證的 02/02 12:27
15F：→ q5332159: 感謝～翻書後清楚多了 02/02 12:35
16F：→ q5332159: 那我可以說algo和ds版的差別是實作上的不同所以一個是wo 02/02 12:36
17F：→ q5332159: rst case一個是amortize嗎？ 02/02 12:36
18F：推 FRAXIS: Fib 的話不論是 algo 或是 ds 應該都是一樣的吧 02/02 12:51
19F：→ q5332159: 啊 我是問binomial 抱歉沒講清楚 02/02 12:52
20F：推 FRAXIS: binomial 的話現在 Algo 應該沒有了吧 舊版的 Algo 02/02 12:54
21F：→ FRAXIS: 是沒有 lazy merge, 所以 insert/merge 都是 02/02 12:55
22F：→ FRAXIS: worst case log n 02/02 12:55
23F：推 FRAXIS: 我直接回文好了 用推文有點難寫 02/02 12:57
24F：→ q5332159: 了解～所以現在只要問binomial就是拿DS來回答吧？>< 02/02 12:57