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

admin2014-01-13 48

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

选项

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

解析

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

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

计算机专业知识

事业单位考试

相关试题推荐

随机试题

最新回复(0)

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

计算机专业知识

事业单位考试

理想的师生关系具备以下几个特征?()

根据罗杰斯的观点，促进学习的心理气氛因素不包括()。

赵明非常害怕狗，教师依次让他选看狗的照片，与他谈论狗，让他远远观看关在笼子里的狗，让他靠近笼中的狗，最后让他摸小狗，抱起小狗，消除了其对狗的恐惧反应，这种改变行为的方法是()。

定量评估，是对工作绩效所进行的质的鉴定，从总体上给予评价，一般常用于职称评审、职务任命、宣传表彰等管理领域。()

不考虑学生的年龄特征，在教育要求、教育教学内容和方法选择上的“一刀切”，违背了个体身心发展的()。

【2014年潍坊市坊子区真题】教师的语言道德修养不包括()。

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

操作性条件反射与经典性条件反射的基本原理是相同的，他们都是随着强化的次数增加而巩固。由于未得到强化而消退。

教学技能这一程序性知识的获得首先要经过陈述性知识的获得阶段，即必须知道“是什么”和“为什么”，然后才能正确和有效地解决“如何做”和“怎么办”的问题。

A．甲巯咪唑B．丙硫氧嘧啶C．普萘洛尔D．复方碘溶液妊娠期甲亢首选抗甲状腺激素药物

较大子宫壁间肌瘤的主要症状为下列哪项

下列改变符合腺性唇炎的临床表现的是

关于对肿瘤的排斥作用，下列那项是正确的

一级公路黄土路堑边坡高度25m时，宜采用()。

最早提出“什么知识最有价值”这一经典课程论命题的学者是()。

WithbutprotectionA.Itusuallygivesinadequate(62)______fromtheweatherB.notonlyinsomedevelopingcountrieswherebic

哪些黏膜病愈合后，可形成明显瘢痕组织的是()。

∣b一a∣+∣c一b∣—∣C∣=a．(1)实数a，b，c在数轴上的位置为(2)实数a，b，c在数轴上的位置为

A、Thewomangetsaticket.B、Themanarreststhewoman.C、Thewomanistakentocourt.D、Thewomanranaway.A选项中的Thewoman，gets