[理工] [DS] 交大100 DS+algo

看板Grad-ProbAsk作者 (可愛小小羅)時間14年前 (2012/02/12 21:37), 編輯推噓2(2推 0噓 6→)
留言8則, 4人參與, 最新討論串2/2 (看更多)
http://www.lib.nctu.edu.tw/attach/download/id-765/ 請問題組18 這演算法是 Sollin's algo 嗎?? (51)的(C)選項要表達的是什麼??? 實在是看不懂 另外(52)關於時間複雜度,該怎麼分析...@@?? 拜託各為了 > < -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.116.82.172
推
02/12 21:58, , 1F
是Sollin 51(C)是說每次contract後點的個數至少少一半
02/12 21:58, 1F
→
02/12 22:33, , 2F
google到mlogn = =
02/12 22:33, 2F
推
02/12 22:37, , 3F
mlongm 當m<<n^2 可寫成mlogn
02/12 22:37, 3F
→
02/12 22:39, , 4F
原來如此 有點頭緒了 感謝樓上幾位^^
02/12 22:39, 4F
→
02/12 22:42, , 5F
每次抓當前所有邊 然後又至少扣一半 所以mlogm這樣嗎?
02/12 22:42, 5F
→
02/12 22:43, , 6F
我也是這樣想的~
02/12 22:43, 6F
→
02/12 22:45, , 7F
每次至少少一半點 共logn iteration
02/12 22:45, 7F
→
02/12 22:45, , 8F
每次iteration至多考慮m個邊
02/12 22:45, 8F
‣ 更多 ai305428d 的文章
文章代碼(AID): #1FDy2TFn (Grad-ProbAsk)
‣ 更多 ai305428d 的文章
文章代碼(AID): #1FDy2TFn (Grad-ProbAsk)