推 ekids1234: 交大的吧 這題後來送分了 09/20 11:36
→ ekids1234: 是說 merge sort 如果說是 Big O(nlogn) 算對嗎 ? 09/20 11:40
→ ekids1234: 原本在想有沒有可能 但merge會切到最後 應該至少theta 09/20 11:41
→ ekids1234: 還是說有可能發生不到 nlogn 的可能性 ? 09/20 11:42
推 joey11121: 感覺不能說at least，因為是theta，不然就要換符號 09/20 13:19
推 mi981027: 感覺他是想考comparison-based sorting algo.的下界是lo 09/20 14:35
→ mi981027: g(n!)而不是nlogn??(前者比後者小一點，所以如果說時間 09/20 14:35
→ mi981027: 至少nlogn就會有問題) 09/20 14:35
→ mi981027: 但偏偏merge sort的執行方式不論是什麼case一律都是nlog 09/20 14:35
→ mi981027: n 所以才會有爭議?? 09/20 14:35
→ mi981027: 同樣覺得是at least那句話有問題但也講不出問題是什麼 09/20 14:35
→ mi981027: merge sort 是O(nlogn)應該是對的吧 09/20 14:35
推 mistel: 我以為是nlogn沒有加上notation XD 09/20 15:44
推 yfancc: 之前聽一個說法說此題前後不應有因果關係，所以爭議 09/20 18:48
→ yfancc: 樓上們的講法都對，不過當初好像是在吵「Thus」這個字不合 09/20 18:49
→ yfancc: 適 09/20 18:49
→ DLHZ: merge的worst/best case都是theta(nlogn)沒問題 09/21 02:57