PTT
Submit
Submit
選擇語言
正體中文
简体中文
PTT
Grad-ProbAsk
[資演] -110交大-資訊聯招
作者:
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)
繼續閱讀
[理工] [資演]-交大111-資訊聯招
ISLAND1999
[理工] [計組] 111成大電機計組 第8題
YoZoR
Re: [理工] 離散 Boolean algebra
deathcustom
[理工] 離散 Boolean algebra
u04fup
[理工] 109 交大計系 15 27
kyh436
111中山資工作業系統
loo80119
[理工] 109 中央 資演選擇對答案
tinhanho
[理工] 111交大OS
ping990579
[理工] 離散數論
foogty
Re: [理工] 100交大 應用數學 第5題
Honor1984
Links
booklink
Contact Us: admin [ a t ] ucptt.com