利用比较的方法进行排序，在最坏情况下，能达到的最好时间复杂度是多少?请给出详细证明。

admin2014-01-13 91

问题利用比较的方法进行排序，在最坏情况下，能达到的最好时间复杂度是多少?请给出详细证明。

选项

答案假定待排序的记录有n个。由于含n个记录的序列可能出现的状态有n!个，则描述n个记录排序过程的判定树必须有n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没有分辨出来。若二叉树高度是h，则叶子结点个数最多为2h-1个；反之，若有u个叶子结点，则二叉树的高度至少有log2tl+1。这就是说，描述n个记录排序的判定树必定存在一条长度为Iog2(n!)的路径，即任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少。根据斯特林公式，有lOg2(n!)=(nlg2r1)，即借助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为(nlog2r1)。

解析

转载请注明原文地址:https://kaotiyun.com/show/PZal777K

本试题收录于：计算机专业知识题库事业单位考试分类

计算机专业知识

事业单位考试

相关试题推荐

随机试题

最新回复(0)

利用比较的方法进行排序，在最坏情况下，能达到的最好时间复杂度是多少?请给出详细证明。

计算机专业知识

事业单位考试

现在很多国家高等教育的发展，都担负着发展科学、产生新的科学知识技术的任务，有建立产学研一体的趋势。这说明()。

从教育系统所赖以运行的时间标准以及建立于其上的产业技术和社会形态出发，我们可以将教育形态划分为()。

学生是班级管理的主体之一。()

相对于直线式编排教材，螺旋式编排教材的优点之一是能够将学生的认知结构与学科的逻辑结构相统一。()

把握问题的本质和关键信息，摒弃无关因素，并在头脑中形成有关问题的初步印象，即形成问题的表征的过程，就是()。

由于先前做了活动或有了经验、习惯的影响而形成的心理的一种动力准备状态称()。

路老师在进行生物课教学的过程中，经常是先给大家讲解知识，然后带大家到植物园里去观察，有时候大家一起进行一些扦插的操作，这样既有课堂知识的学习，又有实际的感性认识，这体现了路老师遵循了教育过程的()。

根据认知心理学家安德森的观点，通过信息加工，人们获得两类知识，即()。

关于子宫肌瘤的声像图表现，错误的是

关于密度分辨率的解释，错误的是

重症肌无力患者出现反拗危象时的正确治疗原则是

确定升降浮沉的依据

因动用而发出无须收回的政府储备物资的，按照发出物资的账面余额，计入()。

下列各项成本中，()不属于酌量性成本。

下列关于xDSL技术的描述中，错误的是()。

Youwillhearaspeakeraddressingagroupofinvestorsattendingaseminartolearnaboutproblemsfacingpotentialexporters.

Oldpeoplearealwayssayingthattheyoungpeoplearenot【51】theywere.Thesamecommentis【52】fromgenerationtogenerationan

ThemajorsourceofincomeofIrishfarmersis______.