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

admin2014-01-13 52

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

选项

答案假定待排序的记录有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——2020年大气污染防治规划》提出要积极调整能源结构，实施煤炭总量控制，力争到()年年底实现煤炭消费总量“不增反降”的历史性转折。

关于教育科研的基本程序，下列最为恰当的是()。

认识和把握教育科研的特点是开展教育科研的基础，关于教育科研的特点，下列表述不正确的是()。

教师权威由角色权威、学术权威和人格权威等构成，其中，对学生进行教学教育的前提是()，教师发挥主导作用的根本是()。

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

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

课程文本一般表现为()。

Wang@cm．hxing．com．cn是一个合法的E-mail地址。()

由于成长环境和性格等方面的不同，人们会形成不同的理想信念；即使同一个人，也会形成关于社会生活不同方面的许多理想信念。这说明理想信念具有

患者，女，54岁。慢性肾炎病史10年。血肌酐为5．5mg／dl，现出现库斯莫尔呼吸。考虑其已出现

乳牙开始萌出的年龄是

某患儿，4岁，持续发热3天，体温40℃，现已出现持续性惊厥，来院救治。针对患儿持续惊厥症状，应给予的药物是

关于施工许可证适用范围的说法，正确的是()。

人(手)孔、通道基础的基础混凝土厚度一般为()mm。

Whatdoesthewomanwantthemantodo?

OnReviewingandImprovingWrittenWorkTeachersfeelveryfrustratedwhentheyfindsmallmistakesinstudents’writing

证明信说明：假设你是公司的经理张青，为李韵提供一份工作证明。内容：1．李韵从2008年6月至2010年7月在本公司担任秘书工作；2．任职期间十分负责任，努力勤奋，善于团队合作；3．公司对她的表现十分满意。

A、Itcanstoremanyinstructions.B、Itcanperformfewtasks.C、Itisasymbolofmodernization.D、Itisascleverashumanbrai