作者qazws3483 (oldguy)
看板Grad-ProbAsk
標題理工
時間Tue Aug 21 11:12:11 2018
https://i.imgur.com/gRqhTHR.jpg
第8.9題要怎麼判斷在worst時是否為linear time?
謝謝各位
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.50.145.161
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1534821133.A.73E.html
1F：推 miachen8604: (8)comparison based的排序的lower bound是nlogn，可 08/21 15:04
2F：→ miachen8604: 以用decision tree證出來，所以worst case一定不可 08/21 15:05
3F：→ miachen8604: 能是linear time 08/21 15:05
4F：推 miachen8604: (9)有一個selection algorithm它的worst case是O(n) 08/21 15:08
5F：→ qazws3483: 感謝樓上大神 我再重看一次筆記有比較懂了 08/22 17:26