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