[理工] 106交大資演9

看板Grad-ProbAsk作者 (chiu)時間5年前 (2019/02/02 11:49), 5年前編輯推噓8(8推 0噓 16→)
留言24則, 4人參與, 5年前最新討論串1/2 (看更多)
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
推
02/02 11:57, 5年前 , 1F
問一下為何algo版是Logn 不是lazy merge嗎
02/02 11:57, 1F
→
02/02 11:59, 5年前 , 2F
lazy merge 不是DS版嗎
02/02 11:59, 2F
→
02/02 12:00, 5年前 , 3F
還是只要是fib就是以DS版為基礎啊？><我疑惑好久了
02/02 12:00, 3F
→
02/02 12:02, 5年前 , 4F
可是我的筆記decrease key的部分又有考慮兩版…@@
02/02 12:02, 4F
→
02/02 12:02, 5年前 , 5F
02/02 12:02, 5F
推
02/02 12:02, 5年前 , 6F
所以algo版不能lazy merge所以跟binomial heap的merge
02/02 12:02, 6F
→
02/02 12:02, 5年前 , 7F
一樣？
02/02 12:02, 7F
推
02/02 12:08, 5年前 , 8F
CLRS p518，用amortized cost O(lgn)，我覺得這種定義問
02/02 12:08, 8F
→
02/02 12:08, 5年前 , 9F
題老師應該比較喜歡用CLRS的定義
02/02 12:08, 9F
推
02/02 12:16, 5年前 , 10F
Fib 的 union 應該都是直接串起來.. 所以一定是O(1) 吧
02/02 12:16, 10F
→
02/02 12:17, 5年前 , 11F
Binomial Heap 的 Merge 才會有 worst case O(lg n)
02/02 12:17, 11F
→
02/02 12:17, 5年前 , 12F
Amortized cost O(1) 的差別
02/02 12:17, 12F
推
02/02 12:27, 5年前 , 13F
我看成b, sorry，CLRS p512裡說union是amortized O(1)，
02/02 12:27, 13F
→
02/02 12:27, 5年前 , 14F
用potential method證的
02/02 12:27, 14F
→
02/02 12:35, 5年前 , 15F
感謝～翻書後清楚多了
02/02 12:35, 15F
→
02/02 12:36, 5年前 , 16F
那我可以說algo和ds版的差別是實作上的不同所以一個是wo
02/02 12:36, 16F
→
02/02 12:36, 5年前 , 17F
rst case一個是amortize嗎？
02/02 12:36, 17F
推
02/02 12:51, 5年前 , 18F
Fib 的話不論是 algo 或是 ds 應該都是一樣的吧
02/02 12:51, 18F
→
02/02 12:52, 5年前 , 19F
啊 我是問binomial 抱歉沒講清楚
02/02 12:52, 19F
推
02/02 12:54, 5年前 , 20F
binomial 的話現在 Algo 應該沒有了吧 舊版的 Algo
02/02 12:54, 20F
→
02/02 12:55, 5年前 , 21F
是沒有 lazy merge, 所以 insert/merge 都是
02/02 12:55, 21F
→
02/02 12:55, 5年前 , 22F
worst case log n
02/02 12:55, 22F
推
02/02 12:57, 5年前 , 23F
我直接回文好了 用推文有點難寫
02/02 12:57, 23F
→
02/02 12:57, 5年前 , 24F
了解～所以現在只要問binomial就是拿DS來回答吧？><
02/02 12:57, 24F
‣ 更多 q5332159 的文章
文章代碼(AID): #1SLHDOmN (Grad-ProbAsk)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共2篇)
‣ 更多 q5332159 的文章
文章代碼(AID): #1SLHDOmN (Grad-ProbAsk)