文章/答案/技术大牛

发布

社区首页 >问答首页 >比较排序算法复杂度

问比较排序算法复杂度
EN

Stack Overflow用户

提问于 2009-12-12 07:17:49

回答 2查看 3.5K关注 0票数 2

为什么基于比较的排序算法的时间复杂度的下界是O( n )？

algorithm

big-o

time-complexity

回答 2

Stack Overflow用户

回答已采纳

发布于 2009-12-12 07:24:05

http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list

我认为，这个问题回答得很好。

票数 7

Stack Overflow用户

发布于 2009-12-12 07:25:50

简而言之，因为你必须查看O(n)的每个元素。对于您查看的每个元素，您必须找出它的顺序是否正确，充其量是O(log )(例如二进制搜索)。因此，净和变为O(n log n)

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/1891506

复制

相似问题

问比较排序算法复杂度
EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问比较排序算法复杂度EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问比较排序算法复杂度
EN