推 tinhanho: median of medians下界不是 O(n)嗎 01/21 23:32
→ tinhanho: 中間的數5個5個排列 應該是O(1)吧 ? 01/21 23:33
推 hensen523: 他是寫omega,而且這問題的下界跟heap sort也沒什麼 01/22 12:56
→ hensen523: 關 01/22 12:56
推 tinhanho: 啊對 下界要用omega 幫我把上面的O換成omega 抱歉 01/22 13:29
→ sweetfat: 好，我再想想，因為他選項中寫heap sort applied 我在想 01/23 09:32
→ sweetfat: 是不是叫我要用heap sort 01/23 09:32
→ hensen523: 我一開始看是沒想那麼多，單純想他說因為使用heap sort 01/23 21:03
→ hensen523: 所以這個問題下界是omega(n)的結論不對 01/23 21:03
→ hensen523: 但即使講heap sort applied，除非他限制就是排完找ith 01/23 21:04
→ hensen523: 不然partition後用heapsort排序跟上面說一樣是omega(n) 01/23 21:06