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