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

admin2014-01-13 28

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

选项

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

解析

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

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

计算机专业知识

事业单位考试

相关试题推荐

随机试题

最新回复(0)

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

计算机专业知识

事业单位考试

班主任要把学生作为交往的主体，研究学生的交往需要，指导学生正确地理解周围的人和事，从而营造良好的()环境。

《中华人民共和国教师法》规定，对教师考核的内容不包括()。

下列选项中，不属于高创造性人才的人格特征是()。

2004年以来我国普通高中课程结构包含的三个层次是()。

习近平访问莫斯科国际关系学院时，在讲话中引用这样一段话：“历史的道路不是涅瓦大街上的人行道，它完全是在田野中前进的，有时穿过尘埃，有时穿过泥泞，有时横渡沼泽，有时行经丛林。”这段话出自()。

魏巍在《我的老师》一文中提到：“我们见了她(蔡老师)不由得就围了上去。即使她写字的时候，我们也默默地看着她，连她握笔的姿势都急于模仿。”这一叙述体现了学生的()特点。

新课程标准将中小学阅读与欣赏放到核心的位置。()

在Word中，若处于插入状态，输入的文本()。

在处方书写中，缩写词“Inj.”代表的含义是

墨菲征阳性常见于以下哪种疾病()

流行性乙型脑炎的炎症性质是

正常婴儿开始能独坐的年龄是

双曲拱桥进行技术状况评定时，主拱圈的构件按拱肋、拱波、横向联结系划分。()

下列边坡支护结构类型中适用于建筑土质边坡高度H≤15m的是()。

个别激励是指_______。

MajesticOceanCruiseLinesOffervalid:June-August2006Enjoya15-dayjourneyaboardtheDiamondCruiserasyouexplo

举一例子说明小学数学概念的形成过程。

已知函数试计算下列各题：S0=∫02f(x)e-xdx