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

admin2014-01-13 77

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

选项

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

解析

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

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

计算机专业知识

事业单位考试

相关试题推荐

随机试题

最新回复(0)

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

计算机专业知识

事业单位考试

人的语言、思维的发展都分别存在着关键期，这说明人的身心发展具有()。

下列关于“出淤泥而不染”的说法，正确的有()。

在宏观上，教与学过程是一个系统过程。下列不属于该系统过程要素的是()。

布鲁纳的结构主义课程论强调中小学教师在课程改革中的重要作用。()

下列关于多元文化基本理念的叙述，正确的是()。

【2013年烟台龙口市真题】教育在个体身心发展中起的作用是无条件的。()

【2014年山东省属真题】王老师观察到，在若干次探究性小组合作学习的讨论环节中，孙丽同学自己总是拿不定主意，要靠同伴拿主意。这说明孙丽的学习风格属于()。

【2015年淄博市真题】当信息从短时记忆进入长时记忆时，信息会发生关键性转变，这一步转变被称为()。

课程标准是各学科的纲领性指导文件，它从整体上规定某门课程的性质及其在课程体系中的地位，规范性确定学科教学目标、内容范围、顺序，是教师教学工作的指南，是编写教科书和测评教学质量的依据。()

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

一病人钡剂胃透检查，见胃壁僵硬胃腔变小，粘膜皱襞大部消失。应诊断为

TheUnitedStates【56】alargepartoftheNorthAmericancontinent.ItsneighborsareCanada【57】thenorth,【58】Mexicotothesout

______travelingbybikehasdisadvantages,italsohasadvantages.

下列关于保险合同的说法中，正确的是()。

一般情况下，4岁半的幼儿经过一年的幼儿园的教育，在与家长或亲人走散的情况下，能够向警察或有关人员说出自己和家长的名字、电话号码等简单信息。()

根据下列资料，回答下列小题。下列说法正确的是()。

若进程P1正在运行，操作系统强行撤下P1进程所占用的CPU，让具有更高优先级的进程P2运行，这种调度方式称为(15)，此时P1进程处于(16)状态。(17)将CPU的时间分成若干个时间片轮流地为各个用户服务。

•Lookatthetablebelow.•Someinformationismissing.•Youwillhearatelephoneconversation.•Foreachquestion