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

admin2014-01-13 37

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

选项

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

解析

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

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

计算机专业知识

事业单位考试

相关试题推荐

随机试题

最新回复(0)

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

计算机专业知识

事业单位考试

下列说法不正确的是()。

表示传统师德非常重视严于律己、身体力行、为人表率的模范作用的先哲名言是()。

关于学习动机与学习效果之间的关系，正确的表述是()。

简述教学评价的分类。

领会知识包括感知、理解教材，感知教材主要是使学生获得关于所学内容的一个整体的表象，理解的目的在于形成概念、原理，认识事物的本质和规律。()

下列文件中，最早提出“把发展基础教育的责任交给地方，有步骤地实行九年义务教育”的是()。

走进某校园，我们看到学生的艺术作品挂在走廊的墙壁上，制作的手工作品放置在展览区，嘉奖优秀学生的信息张贴在显眼的位置。这主要体现了道德教育的()。

命令一致原理，是指主管人员在实现目标过程中下达的各种命令越是一致，个人在执行命令中发生矛盾就越小，领导与被领导双方对最终成果的责任感也就越小。()

记录讲话时，把可有可无或重复的语句删去，尽可能做到既要注重精，还要注重详，需采用()记录法。

某公司为了寻找改进管理的途径召开头脑风暴法的会议。在会议上大家各抒己见，但是少数人提出的方法荒诞不经，甚至有时让人感觉离题太远。对于这种情况你应该如何处理?()

对于办理完毕的公文处理环节有()

与口腔黏膜感染有关的疱疹病毒包括

以下税金进入产品成本的是()。

美国的证券交易场外市场被称为()。

为了提高教师的积极性、创造性，增强教师的事业心、责任心，教师考核应注意遵循下列哪些原则?()

人民政协以政治协商和民主监督作为自己的主要职能。民主监督主要是指

10件产品中4件为次品，6件为正品，现抽取2件产品．在第一件为正品的情况下，求第二件为次品的概率；

Whatcanweinferfromthesentence"Becausetheytrembleatthethoughtofbeingseeninpublicinclothesthatareoutoffash

Storagewillbe______oneachpieceofluggageremainingatstationsover24hours.