Re: [理工] 106交大资演9 FRAXIS PTT批踢踢实业坊

Re: [理工] 106交大资演9

楼主: FRAXIS (喔喔) 2019-02-02 13:25:23

※ 引述《q5332159 (chiu)》之铭言：
: http://i.imgur.com/GCwu6aO.jpg
: 想问这题的d～
: algo版是O(log n) DS版是O(1)
: 不知道应该要以哪种作为答案@@
: 还有想问大家遇到问binomial heap或fib heap的时候都会以algo版来回答还是DS版啊？><
: 先谢谢各位～～
:

作者: S2067030 (Ep.Yao) 2019-02-02 13:40:00

先推，谢谢大大特地回文解释

作者: q5332159 (chiu) 2019-02-02 14:21:00

好详细！太感谢你了！！

作者: DLHZ ( ) 2019-02-02 16:08:00

为什么还要分算法版跟资料结构版

作者: eigen555 (一一一) 2019-02-02 17:20:00

那请问decrease-key的worst case呢我感觉不是O(1)啊因为他不是问amortize

作者: S2067030 (Ep.Yao) 2019-02-02 17:32:00

楼上你是问bino还是fib，bino是O(logn)，fib是O(1)

作者: eigen555 (一一一) 2019-02-02 17:38:00

喔喔我是想问Fib

作者: S2067030 (Ep.Yao) 2019-02-02 17:41:00

他可以直接对你想Decrease的值做运算，所以O(1)然后因为它采用lazy merge，所以如果你减过头了破坏结构会直接被拉出来，不合并，所以有没有amor都是O(1)还是不懂再说我在想怎解释，这部分刘逸上课有特别提醒

作者: alen0303 (艾伦零参智商负三) 2019-02-02 21:00:00

推整理

楼主: FRAXIS (喔喔) 2019-02-03 00:41:00

有人问 DecreaseKey 所以补充一下

作者: eigen555 (一一一) 2019-02-03 13:31:00

感谢

作者: a28238341a (小蜗) 2019-02-03 17:00:00

推推时间整理很用心感谢!

作者: skyHuan (Huan) 2019-02-03 17:44:00

推推

继续阅读

Re: [理工] 108中央离散第一题ERT312 [理工] 106交大资演9q5332159 [理工] 请教一些数学符号rogerexe [理工] 106北大资结 LCSncdonalds123 [理工] 数学基本观念kaidi620 [理工] set associative cache entry问题yushes7627fn [理工] 离散下树 QoGIVoQ [商管] 102中山资结Voicer [理工] 交大105计系21q5332159 [理工] 107 中山热力学b321054