[资演] -110交大-资讯联招 sweetfat PTT批踢踢实业坊

楼主: sweetfat (有种东西叫运气) 2023-01-21 22:34:18

https://i.imgur.com/g1mDJKL.jpg
如题，答案没有给D，我的理解是heap sort在worst case 也是nlogn，请问D选项是错哪边呢？

作者: tinhanho (hanoho) 2023-01-21 23:32:00

median of medians下界不是 O(n)吗中间的数5个5个排列应该是O(1)吧 ?

作者: hensen523 2023-01-22 12:56:00

他是写omega,而且这问题的下界跟heap sort也没什么关

作者: tinhanho (hanoho) 2023-01-22 13:29:00

啊对下界要用omega 帮我把上面的O换成omega 抱歉

楼主: sweetfat (有种东西叫运气) 2023-01-23 09:32:00

好，我再想想，因为他选项中写heap sort applied 我在想是不是叫我要用heap sort

作者: hensen523 2023-01-23 21:03:00

我一开始看是没想那么多，单纯想他说因为使用heap sort所以这个问题下界是omega(n)的结论不对但即使讲heap sort applied，除非他限制就是排完找ith不然partition后用heapsort排序跟上面说一样是omega(n)

继续阅读