推 tanktankl5:感謝指導!! 謝謝 01/27 23:33
※ 引述《tanktankl5 (同燕皮=剎車皮)》之銘言：
: 第2-3題
: 題目:The time complexity of sorting 2 n-element sequences
: can be as efficient as (A)O(n) (B)O(nlogn) (C)O(n^2) (D)O(n^3)
: 答案是:B
: 我原本想法是:N筆資料排序，用高等sort平均時間可到達 nlogn
: 但是後來同學說，那若是用counting sort呢?不就O(n)嗎?
: 或者是我們都想錯了呢?懇請高手指教
因為那些linear time sort的演算法
必須要"事先"知道一些資訊
像你提到的counting sort
這個就必須先知道key值的range才行
但是題目並沒有說事先已知道這些資訊
所以還是選comparsion sort的下限比較好
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.24.12