[資演] -110交大-資訊聯招

看板Grad-ProbAsk作者 (有種東西叫運氣)時間1年前 (2023/01/21 22:34), 編輯推噓3(3推 0噓 8→)
留言11則, 3人參與, 1年前最新討論串1/1
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://www.ptt.cc/bbs/Grad-ProbAsk/M.1674311660.A.F8E.html
推
01/21 23:32, 1年前 , 1F
median of medians下界不是 O(n)嗎
01/21 23:32, 1F
→
01/21 23:33, 1年前 , 2F
中間的數5個5個排列 應該是O(1)吧 ?
01/21 23:33, 2F
推
01/22 12:56, 1年前 , 3F
他是寫omega,而且這問題的下界跟heap sort也沒什麼
01/22 12:56, 3F
→
01/22 12:56, 1年前 , 4F
關
01/22 12:56, 4F
推
01/22 13:29, 1年前 , 5F
啊對 下界要用omega 幫我把上面的O換成omega 抱歉
01/22 13:29, 5F
→
01/23 09:32, 1年前 , 6F
好，我再想想，因為他選項中寫heap sort applied 我在想
01/23 09:32, 6F
→
01/23 09:32, 1年前 , 7F
是不是叫我要用heap sort
01/23 09:32, 7F
→
01/23 21:03, 1年前 , 8F
我一開始看是沒想那麼多，單純想他說因為使用heap sort
01/23 21:03, 8F
→
01/23 21:03, 1年前 , 9F
所以這個問題下界是omega(n)的結論不對
01/23 21:03, 9F
→
01/23 21:04, 1年前 , 10F
但即使講heap sort applied，除非他限制就是排完找ith
01/23 21:04, 10F
→
01/23 21:06, 1年前 , 11F
不然partition後用heapsort排序跟上面說一樣是omega(n)
01/23 21:06, 11F
‣ 更多 sweetfat 的文章
文章代碼(AID): #1Zo_Vi-E (Grad-ProbAsk)