首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
admin
2019-08-01
38
问题
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
选项
答案
假定待排序的记录有n个。由于含n个记录的序列可能出现的状态有n!个，则描述n个记录排序过程的判定树必须有n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没有分辨出来。我们知道，若二叉树高度是h，则叶子结点个数最多为2
h-1
；反之，若有u个叶子结点，则二叉树的高度至少为(log
2
u)+1。这就是说，描述n个记录排序的判定树必定存在一条长度为log
2
(n!)的路径。即任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少是log
2
(n!)。根据斯特林公式，有log
2
(n!)=O(nlog
2
n)。即借助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为O(nlog
2
n)。 提示：此题考查的知识点是基于比较的排序算法效率。
解析
转载请注明原文地址:https://kaotiyun.com/show/3ACi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
真理标准问题大讨论
下列有关元朝民族关系的叙述，不正确的是()。
租庸调制对农业生产的最大作用是()。
我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说，如炎帝和黄帝两个部落曾战于()，结果黄帝取得了胜利。
1940年毛泽东的《新民主主义论》:“而所谓民主主义，现在已不是旧范畴的民主主义，已不是日民主主义，而是新范畴的民主主义，而是新民主主义”。毛泽东分民主革命的两个阶段主要依据是
全国高校院系调整的具体时间是()。
新文化运动前期的指导思想是()。
新文化运动前期的指导思想是()。
对斯大林时期形成的高度集中的社会主义经济政治体制的叙述，不确切的是()。
指令系统字长16位，每个地址码为6位，采用扩展操作码的方式，试设计14条二地址指令，100条一地址指令，100条零地址指令。(1)画出操作码的扩展形式。(2)下图为指令译码逻辑图，其中只给出了二地址指令的译码逻辑，试补全一地址指令和零地址指令的
随机试题
A500～1000gB500～800gC340～450gD800～1100gE1200～1700g
雷诺综合征，指(趾)缺血，由白变紫变红，随后转暖，典型发作过程一般持续
继发不孕相对不孕
在—行政诉讼案中，被告方某行政机关委托刘律师担任诉讼代理人。刘律师为使案件胜诉，诉讼期间调查收集了充分的证据材料。下列关于刘律师做法的选项哪个是正确的?()
账套启用后，核算信息和基础设置信息不允许修改。()
AS公司属于高新技术企业，适用的所得税税率为15％，2015年12月31日预计2015年以后不再属于高新技术企业，且所得税税率将变更为25％。(1)2015年1月1日期初余额资料：递延所得税负债期初余额为30万元(即因上年交易性金融资产产生应纳税暂时性差
A、 B、 C、 D、 B本题属于空间重构类，主要考察了双面之间的相对关系和相邻关系。第一组图形中，第一个图形是平面图形，第二个、第三个图形是该图形的折叠图形；第二组图形中，根据第二个折叠图形中黑底白三角特正
Whatisthetopicofthisconversation?
•Youwillhearpartofaconversationbetweentwocompanyemployees,awomancalledRoseandamancalledSteve.•Foreachque
WhatdoSharonandXiaoLiagreewasthestrongestaspectoftheirpresentation?
最新回复
(
0
)
