首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
admin
2019-01-16
33
问题
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
选项
答案
假定待排序的记录有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://jikaoti.com/ti/23fjFFFM
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
魏晋南北朝的手工业技术有所进步，下列各项能反映这一特点的是()。①培育出“三熟之稻”②“灌钢”技术的发明③吴培育出八辈之蚕④纸成为最主要的书写材料
关于希腊早期宗教的叙述不正确的是()。
在下列各项中，不属于列宁《四月提纲》内容的是()。
下列不属于“四清运动”内容的是()。
简述布匿战争的过程。
试述北伐战争的过程以及胜利的原因。
“二战”后，联合国的成立反映了世界人民和平的愿望，下列叙述正确的是()。
简述美、苏争霸的三个阶段及特点。
第一次国共合作采取了共产党员以个人身份加入国民党的“党内合作”方式。最早提出这种方式的是()。
假设系统的所有资源是同类型的，系统中的进程每次申请资源数最多1个，那么，下面列出的4种情况中，()可能发生死锁。情况序号系统中进程数资源总量
随机试题
一件行政诉讼案件中，被告响水县建设局，于2008年7月13日颁发给第三人响水县亨达房地产开发有限公司编号为040039建设工程规划许可证，许可第三人在本县城军民东路段开发房地产，其许可附件军民东路1号综合楼建设工程施工图纸（200436号图纸）设计在原告门
姜科植物来源的果实类药材有
患者，男性，50岁，因突发性中上腹剧痛10小时来院急诊，体检发现有板样腹．腹部平片示膈下有游离气体，生命体征平稳。既往有消化性溃疡和不规则服药史。应为该患者采取的首要措施为()。
所谓工程建设勘察是指()。
报关员调动工作单位时，应持()的证明文件向所在地海关办理重新注册手续。
在()情况下，熊市套利可以获利。
对某单位的100名员工进行调查，结果发现他们喜欢看球赛、电影和戏剧。其中58人喜欢看球赛，38人喜欢看戏剧，52人喜欢看电影，既喜欢看球赛又喜欢看戏剧的有18人，既喜欢看电影又喜欢看戏剧的有16人，三种都喜欢看的有12人，则只喜欢看电影的有多少人?(
通常的工作计划中都指明一段时期预先决定()等具体问题。
根据香农公式，以下关系正确的是()。
输入掩码字符“＆”的含义是
最新回复
(
0
)
