有没有办法显示最差的基于比较的排序情况的上限？是不是完全依赖于实现？我可以很好地设计一个代码，将数组的每个元素与每个其他元素进行比较 . 这将是低效的，但它不会是错误的 .
因此，对于最坏情况（即Ω（n log n））的最紧密下限，是否也存在任何最严格的上限？
没有基于最坏情况比较的排序的下限是 O(n log n) . 请参阅wikipedia以获取简短证明 . 或Introduction to Algorithms中的定理8.1（单击顶部的下一个） .
O(n log n)
等等我误读了你的问题 . 你不能有一个最严格的上限，因为你总是可以使你的算法更复杂，但是你可以证明，对于每个基于比较的排序算法，存在一个最坏的情况，至少需要 O(n log n) （通常最多）比较 .
1 回答
没有基于最坏情况比较的排序的下限是
O(n log n). 请参阅wikipedia以获取简短证明 . 或Introduction to Algorithms中的定理8.1（单击顶部的下一个） .等等我误读了你的问题 . 你不能有一个最严格的上限，因为你总是可以使你的算法更复杂，但是你可以证明，对于每个基于比较的排序算法，存在一个最坏的情况，至少需要
O(n log n)（通常最多）比较 .