[理工] 資結觀念

看板Grad-ProbAsk作者 (加州貓)時間11年前 (2015/02/03 11:18), 11年前編輯推噓5(5推 0噓 2→)
留言7則, 6人參與, 最新討論串1/1
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
推
02/03 11:56, , 1F
對吧，如果是只看best case，就跟你說的一樣
02/03 11:56, 1F
→
02/03 12:00, , 2F
應該是true(不需要sort) 你戰友應該是有寫過'worst' case
02/03 12:00, 2F
→
02/03 12:01, , 3F
Ω 給你符號XD
02/03 12:01, 3F
推
02/03 15:22, , 4F
True
02/03 15:22, 4F
推
02/03 18:47, , 5F
你是對得
02/03 18:47, 5F
推
02/03 19:01, , 6F
bubble要加上停止條件才能到best case O(n)喔
02/03 19:01, 6F
推
02/04 11:01, , 7F
是問best case就對, avg. case只能到Theta(nlgn)
02/04 11:01, 7F
※ 編輯: CaliforCat (111.243.118.248), 02/04/2015 14:14:41
‣ 更多 CaliforCat 的文章
文章代碼(AID): #1Kq3tsHO (Grad-ProbAsk)