基于比较的排序的时间复杂度下限是多少
答案:2 悬赏:70 手机版
解决时间 2021-12-03 02:22
- 提问者网友：精神病院里
- 2021-12-02 08:52
基于比较的排序的时间复杂度下限是多少
最佳答案
- 五星知识达人网友：等灯
- 2021-12-02 09:28
原因：
对于n个待排序元素，在未比较时，可能的正确结果有n!种。
在经过一次比较后，其中两个元素的顺序被确定，所以可能的正确结果剩余n!/2种。
依次类推，直到经过m次比较，剩余可能性n!/(2^m)种。
直到n!/(2^m)<=1时，结果只剩余一种。此时的比较次数m为o(nlogn)次。
所以基于排序的比较算法，最优情况下，复杂度是o(nlogn)的。
对于n个待排序元素，在未比较时，可能的正确结果有n!种。
在经过一次比较后，其中两个元素的顺序被确定，所以可能的正确结果剩余n!/2种。
依次类推，直到经过m次比较，剩余可能性n!/(2^m)种。
直到n!/(2^m)<=1时，结果只剩余一种。此时的比较次数m为o(nlogn)次。
所以基于排序的比较算法，最优情况下，复杂度是o(nlogn)的。
全部回答
- 1楼网友：神的生死簿
- 2021-12-02 11:03
基于比较的排序算法是不能突破O(NlogN)的。简单证明如下：
N个数有N!个可能的排列情况，也就是说基于比较的排序算法的判定树有N!个叶子结点，比较次数至少为log(N!)=O(NlogN)(斯特林公式)。
N个数有N!个可能的排列情况，也就是说基于比较的排序算法的判定树有N!个叶子结点，比较次数至少为log(N!)=O(NlogN)(斯特林公式)。
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯