3

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

4

2 回答 2

7

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

我认为很好地回答了这个问题。

于 2009-12-11T23:24:04.773 回答
1

简而言之，因为您必须查看 O(n) 的每个元素。对于您查看的每个元素，您必须确定其顺序是否正确，最多为 O(log n)（例如二进制搜索）。所以净总和变为 O(n log n)

于 2009-12-11T23:25:49.700 回答