[資演] -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)

繼續閱讀