[理工] 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来回答吧？><

继续阅读