1. PTT
  2. Grad-ProbAsk

理工

楼主: qazws3483 (oldguy)   2018-08-21 11:12:11
https://i.imgur.com/gRqhTHR.jpg
第8.9题要怎么判断在worst时是否为linear time?
谢谢各位
作者: miachen8604 (这个U戏有必胜法)   2018-08-21 15:04:00
(8)comparison based的排序的lower bound是nlogn，可以用decision tree证出来，所以worst case一定不可能是linear time(9)有一个selection algorithm它的worst case是O(n)
楼主: qazws3483 (oldguy)   2018-08-22 17:26:00
感谢楼上大神 我再重看一次笔记有比较懂了
继续阅读
[理工] 离散-转换法求递回关系式aa13579zz[理工] 网络路径走访eduzone[理工] 线代 代数重数！Aa841018[理工] 算法devide and conquer 105清大wilson50101[理工] 离散 两题排列组合AAQ8[理工] 线代 子空间必要条件befdawn[理工] 线代 子空间证明befdawn[理工] 线代 T or F 证明题的疑问st945712[理工] 离散 组合AAQ8[理工] 离散 乱序及禁位AAQ8

Links booklink

Contact Us: admin [ a t ] ucptt.com