[理工] 106交大資演9 q5332159 PTT批踢踢實業坊

作者: q5332159 (chiu) 2019-02-02 11:49:41

http://i.imgur.com/GCwu6aO.jpg
想問這題的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的部分又有考慮兩版…@@http://i.imgur.com/nw6uTFj.jpg

作者: 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來回答吧？><

繼續閱讀