[理工] 資結觀念

[CaliforCat (加州貓)]

True or False
The best case time complexity of a comparison-based sorting algorithm can
achieve O(n).

戰友覺得是Flase，應該Ω(nlogn)才對
我的想法覺得True，因為insertion跟bubble sort的best case是O(n)

不知道這題該怎麼想才對
謝謝！

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.188.203
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1422933494.A.458.html
推 GuardmanMart: 對吧，如果是只看best case，就跟你說的一樣
→ asjh612: 應該是true(不需要sort) 你戰友應該是有寫過'worst' case
→ asjh612: Ω 給你符號XD
推 hyc1227: True
推 clarkman: 你是對得
推 RancoonYuan: bubble要加上停止條件才能到best case O(n)喔
推 mkchiun1028: 是問best case就對, avg. case只能到Theta(nlgn)
※ 編輯: CaliforCat (111.243.118.248), 02/04/2015 14:14:41