本文主要是介绍比较排序算法的时间复杂度的下限，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原因：
对于n个待排序元素，在未比较时，可能的正确结果有n!种。
在经过一次比较后，其中两个元素的顺序被确定，所以可能的正确结果剩余n!/2种（确定之前两个元素的前后位置的情况是相同，确定之后相当于少了一半的可能性）。
依次类推，直到经过m次比较，剩余可能性n!/(2^m)种。
直到n!/(2^m)<=1时，结果只剩余一种。根据斯特灵公式，此时的比较次数m为o(nlogn)次。
所以基于排序的比较算法，最优情况下，复杂度是o(nlogn)的。
这篇关于比较排序算法的时间复杂度的下限的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
