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