理工 qazws3483 PTT批踢踢實業坊

理工

作者: 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

Contact Us: admin [ a t ] ucptt.com