首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
admin
2019-01-16
71
问题
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
选项
答案
假定待排序的记录有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://www.kaotiyun.com/show/glRi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下面有关兵制的内容，与唐玄宗有关的是()
下列内容不属于《大宪章》内容的是()。
下列关于罗马共和国政治制度的叙述，不正确的是()。
阅读下列史料，并回答问题：在琶勒尼斯(注：地名)一役获胜后，他(庇西特拉图)便占领政府，并解除人民武装；现在他已能稳定地握住僭主政权，并且取得那克索斯。以吕格达密斯为统治者。他解除人民武装的方法是这样的：他在塞修斯庙举行了一个武装的阅兵式，同时举行一次民
下列选项中，不属于列宁《四月提纲》内容的是()。
简述中共八大的内容以及主要历史功绩。
论述秦国商鞅变法的内容、过程以及重要意义。
简述汉光武帝加强中央集权制度的措施。
材料一材科二(戈尔巴乔夫政府)在制定改革政策方针中存在三个严重问题：第一，仍然以优先发展重工业和机器制造业为主的“加速发展战略”作为发展资本密集型产业的主要战略，已不符合时代潮流。现代经济结构已由资本密集型向技术密集型发展……苏联的经济改革对
下列对近代社会思潮产生的先后顺序排列正确的是()。①人文主义②自由主义③理性主义④重商主义
随机试题
下列有关纤连蛋白的叙述，错误的是
脊髓腔穿刺术后的患者可因脑压过低引起头痛，其主要机制是
根据牛腿的裂缝控制要求，牛腿的高度与下列( )项数值最为接近。若截面的有效高度h0=810mm，则纵向受拉钢筋的截面面积与下列( )项数值最为接近。
下列施工现场防止噪声污染的措施中，最根本的措施是()。
在导游的职业行为规范中，()是各国伦理道德的核心，是导游人员必备的情操修养，也是合格导游人员的首要条件。
教学过程是教师有目的、有计划地引导学生掌握科学文化基础知识和基本技能，逐步养成辩证唯物主义世界观和共产主义道德品质的过程。这一观点属于()。
影响教师职业发展时间进程和质量水平的主要因素是()
关于个人与环境的关系，社会工作的专业观点认为()。
一个好的学者，要么具有很好的学术天赋，要么是经过了长期不懈的后天努力。金灵先生终身致力于学术研究，那么()
下面程序运行后,单击命令按钮,输出的结果是【】PrivateSubCommand1_Click()Dima%(1To4),b%(2To6),i%,str1#,str2#Fori=1To4a(i)=iNe
最新回复
(
0
)
