作者sweetfat (有種東西叫運氣)
看板Grad-ProbAsk
標題[資演] -110交大-資訊聯招
時間Sat Jan 21 22:34:18 2023
https://i.imgur.com/g1mDJKL.jpg
如題，答案沒有給D，我的理解是heap sort在worst case 也是nlogn，請問D選項是錯哪邊呢？
-----
Sent from JPTT on my iPhone
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.169.136.122 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1674311660.A.F8E.html
1F：推 tinhanho: median of medians下界不是 O(n)嗎 01/21 23:32
2F：→ tinhanho: 中間的數5個5個排列 應該是O(1)吧 ? 01/21 23:33
3F：推 hensen523: 他是寫omega,而且這問題的下界跟heap sort也沒什麼 01/22 12:56
4F：→ hensen523: 關 01/22 12:56
5F：推 tinhanho: 啊對 下界要用omega 幫我把上面的O換成omega 抱歉 01/22 13:29
6F：→ sweetfat: 好，我再想想，因為他選項中寫heap sort applied 我在想 01/23 09:32
7F：→ sweetfat: 是不是叫我要用heap sort 01/23 09:32
8F：→ hensen523: 我一開始看是沒想那麼多，單純想他說因為使用heap sort 01/23 21:03
9F：→ hensen523: 所以這個問題下界是omega(n)的結論不對 01/23 21:03
10F：→ hensen523: 但即使講heap sort applied，除非他限制就是排完找ith 01/23 21:04
11F：→ hensen523: 不然partition後用heapsort排序跟上面說一樣是omega(n) 01/23 21:06