[理工] 106交大資演9
作者: q5332159 (chiu) 2019-02-02 11:49:41
想問這題的d～
algo版是O(log n) DS版是O(1)
不知道應該要以哪種作為答案@@
還有想問大家遇到問binomial heap或fib heap的時候都會以algo版來回答還是DS版啊？><
先謝謝各位～～
作者: eric131204 (暗女巫) 2019-02-02 11:57:00
問一下為何algo版是Logn 不是lazy merge嗎
作者: q5332159 (chiu) 2019-02-02 11:59:00
lazy merge 不是DS版嗎還是只要是fib就是以DS版為基礎啊？><我疑惑好久了可是我的筆記decrease key的部分又有考慮兩版…@@![]()
" target="_blank" rel="nofollow">
![]()
" target="_blank" rel="nofollow">作者: eric131204 (暗女巫) 2019-02-02 12:02:00
所以algo版不能lazy merge所以跟binomial heap的merge一樣？
作者: plsmaop (plsmaop) 2019-02-02 12:08:00
CLRS p518，用amortized cost O(lgn)，我覺得這種定義問題老師應該比較喜歡用CLRS的定義
作者: FRAXIS (喔喔) 2019-02-02 12:16:00
Fib 的 union 應該都是直接串起來.. 所以一定是O(1) 吧Binomial Heap 的 Merge 才會有 worst case O(lg n)Amortized cost O(1) 的差別
作者: plsmaop (plsmaop) 2019-02-02 12:27:00
我看成b, sorry，CLRS p512裡說union是amortized O(1)，用potential method證的
作者: q5332159 (chiu) 2019-02-02 12:35:00
感謝～翻書後清楚多了那我可以說algo和ds版的差別是實作上的不同所以一個是worst case一個是amortize嗎？
作者: FRAXIS (喔喔) 2019-02-02 12:51:00
Fib 的話不論是 algo 或是 ds 應該都是一樣的吧
作者: q5332159 (chiu) 2019-02-02 12:52:00
啊 我是問binomial 抱歉沒講清楚
作者: FRAXIS (喔喔) 2019-02-02 12:54:00
binomial 的話現在 Algo 應該沒有了吧 舊版的 Algo是沒有 lazy merge, 所以 insert/merge 都是worst case log n我直接回文好了 用推文有點難寫
作者: q5332159 (chiu) 2019-02-02 12:57:00
了解～所以現在只要問binomial就是拿DS來回答吧？><