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