作者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/cn.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