[理工] 資結_排序小問題

看板Grad-ProbAsk作者 (fmtshk)時間6年前 (2019/09/20 11:32), 編輯推噓5(5推 0噓 12→)
留言17則, 6人參與, 6年前最新討論串1/1
https://i.imgur.com/s15LYvD.jpg
請問(b)為何錯了？ 難道是英文裡有鬼？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.242.102.202 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1568950344.A.951.html
推
09/20 11:36, 6年前 , 1F
交大的吧 這題後來送分了
09/20 11:36, 1F
→
09/20 11:40, 6年前 , 2F
是說 merge sort 如果說是 Big O(nlogn) 算對嗎 ?
09/20 11:40, 2F
→
09/20 11:41, 6年前 , 3F
原本在想有沒有可能 但merge會切到最後 應該至少theta
09/20 11:41, 3F
→
09/20 11:42, 6年前 , 4F
還是說有可能發生不到 nlogn 的可能性 ?
09/20 11:42, 4F
推
09/20 13:19, 6年前 , 5F
感覺不能說at least，因為是theta，不然就要換符號
09/20 13:19, 5F
推
09/20 14:35, 6年前 , 6F
感覺他是想考comparison-based sorting algo.的下界是lo
09/20 14:35, 6F
→
09/20 14:35, 6年前 , 7F
g(n!)而不是nlogn??(前者比後者小一點，所以如果說時間
09/20 14:35, 7F
→
09/20 14:35, 6年前 , 8F
至少nlogn就會有問題)
09/20 14:35, 8F
→
09/20 14:35, 6年前 , 9F
但偏偏merge sort的執行方式不論是什麼case一律都是nlog
09/20 14:35, 9F
→
09/20 14:35, 6年前 , 10F
n 所以才會有爭議??
09/20 14:35, 10F
→
09/20 14:35, 6年前 , 11F
同樣覺得是at least那句話有問題但也講不出問題是什麼
09/20 14:35, 11F
→
09/20 14:35, 6年前 , 12F
merge sort 是O(nlogn)應該是對的吧
09/20 14:35, 12F
推
09/20 15:44, 6年前 , 13F
我以為是nlogn沒有加上notation XD
09/20 15:44, 13F
推
09/20 18:48, 6年前 , 14F
之前聽一個說法說此題前後不應有因果關係，所以爭議
09/20 18:48, 14F
→
09/20 18:49, 6年前 , 15F
樓上們的講法都對，不過當初好像是在吵「Thus」這個字不合
09/20 18:49, 15F
→
09/20 18:49, 6年前 , 16F
適
09/20 18:49, 16F
→
09/21 02:57, 6年前 , 17F
merge的worst/best case都是theta(nlogn)沒問題
09/21 02:57, 17F
‣ 更多 fmtshk 的文章
文章代碼(AID): #1TX4X8bH (Grad-ProbAsk)