理工

[qazws3483 (oldguy)]

https://i.imgur.com/gRqhTHR.jpg
第8.9題要怎麼判斷在worst時是否為linear time?
謝謝各位

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.50.145.161
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1534821133.A.73E.html
推 miachen8604: (8)comparison based的排序的lower bound是nlogn，可
→ miachen8604: 以用decision tree證出來，所以worst case一定不可
→ miachen8604: 能是linear time
推 miachen8604: (9)有一個selection algorithm它的worst case是O(n)
→ qazws3483: 感謝樓上大神 我再重看一次筆記有比較懂了