基于比较的任一排序算法，在平均情况下的比较次数至少是多少
答案:1 悬赏:40 手机版
解决时间 2021-11-16 17:13
- 提问者网友：沉默的哀伤
- 2021-11-16 13:19
基于比较的任一排序算法，在平均情况下的比较次数至少是多少
最佳答案
- 五星知识达人网友：低音帝王
- 2021-11-16 14:35
评价所需比较次数至少为O(nlog n)
简单来说n个数共有n!种排列 一次比较最多从中排除一半的可能性
共至少需要 log n! 次比较 用stirling公式近似阶乘后就是这个结果
具体证明题主可以去看《算法导论》排序那章
简单来说n个数共有n!种排列 一次比较最多从中排除一半的可能性
共至少需要 log n! 次比较 用stirling公式近似阶乘后就是这个结果
具体证明题主可以去看《算法导论》排序那章
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息
大家都在看
推荐资讯