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