[理工] 106交大資演9

[q5332159 (chiu)]

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1549079384.A.C17.html
※ 編輯: q5332159 (39.12.160.203), 02/02/2019 11:51:38
推 eric131204: 問一下為何algo版是Logn  不是lazy merge嗎
→ q5332159: lazy merge 不是DS版嗎
→ q5332159: 還是只要是fib就是以DS版為基礎啊？><我疑惑好久了
→ q5332159: 可是我的筆記decrease key的部分又有考慮兩版…@@
→ q5332159: http://i.imgur.com/nw6uTFj.jpg
推 eric131204: 所以algo版不能lazy merge所以跟binomial heap的merge
→ eric131204: 一樣？
推 plsmaop: CLRS p518，用amortized cost O(lgn)，我覺得這種定義問
→ plsmaop: 題老師應該比較喜歡用CLRS的定義
推 FRAXIS: Fib 的 union 應該都是直接串起來.. 所以一定是O(1) 吧
→ FRAXIS: Binomial Heap 的 Merge 才會有 worst case O(lg n)
→ FRAXIS: Amortized cost O(1) 的差別
推 plsmaop: 我看成b, sorry，CLRS p512裡說union是amortized O(1)，
→ plsmaop: 用potential method證的
→ q5332159: 感謝～翻書後清楚多了
→ q5332159: 那我可以說algo和ds版的差別是實作上的不同所以一個是wo
→ q5332159: rst case一個是amortize嗎？
推 FRAXIS: Fib 的話不論是 algo 或是 ds 應該都是一樣的吧
→ q5332159: 啊 我是問binomial 抱歉沒講清楚
推 FRAXIS: binomial 的話現在 Algo 應該沒有了吧 舊版的 Algo
→ FRAXIS: 是沒有 lazy merge, 所以 insert/merge 都是
→ FRAXIS: worst case log n
推 FRAXIS: 我直接回文好了 用推文有點難寫
→ q5332159: 了解～所以現在只要問binomial就是拿DS來回答吧？><