作者cansister (cansister)
看板Grad-ProbAsk
標題[理工] [algo]- sorting
時間Tue Jan 5 00:27:01 2010
Please answer "True" or "False" for the following questions.
1. The lower bound of worst case time complexity of sort algorithms isΩ(nlogn)
ANS: False
除了counting sort以外，其他的演算法的worst case的最佳時間複雜度應該是nlogn，
一般而言應該是不考慮counting sort的，不是嗎？
不知道該怎麼解釋，謝謝指教。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.134.129.184
1F：→ aey:"comparison based" sorting algo 下限才為Ω(nlogn) 01/05 01:07
2F：→ cansister:瞭解了 謝謝你 01/05 04:47
3F：推 assassin88:這題答案不是ture嗎？ 01/06 00:10
4F：→ FRAXIS:我也覺得是True 一般來說都是討論Comparison Based.. 01/06 09:20
5F：→ cansister:我看到的講義答案寫false....不知道哪個才對 01/07 00:52