作者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/cn.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