首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
公务员
利用比较的方法进行排序,在最坏情况下,能达到的最好时间复杂度是多少?请给出详细证明。
利用比较的方法进行排序,在最坏情况下,能达到的最好时间复杂度是多少?请给出详细证明。
admin
2014-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.
下列关于保险合同的说法中,正确的是()。
Y公司是一家制作紫砂陶的家族企业。紫砂陶制作以特产于当地的一种具有特殊团粒结构和双重气孔结构的紫砂泥料为原料,采用百种以上的自制工具,经过打泥片、拍打身筒、镶接身筒或镶接与雕塑结合等步骤最终完成陶制品。该公司成立80多年来,经过世代相传积累了丰富的紫砂陶制
居民个人王某及其配偶名下均无住房,在某省会工作并租房居住,2019年9月开始攻读工商管理硕士。2020年王某收入及部分支出如下:(1)王某每月从单位领取扣除社会保险费用及住房公积金后的收入为8000元,截至11月累计已经预扣预缴个人所得税税款363元。
一般情况下,4岁半的幼儿经过一年的幼儿园的教育,在与家长或亲人走散的情况下,能够向警察或有关人员说出自己和家长的名字、电话号码等简单信息。()
根据下列资料,回答下列小题。下列说法正确的是()。
若进程P1正在运行,操作系统强行撤下P1进程所占用的CPU,让具有更高优先级的进程P2运行,这种调度方式称为(15),此时P1进程处于(16)状态。(17)将CPU的时间分成若干个时间片轮流地为各个用户服务。
•Lookatthetablebelow.•Someinformationismissing.•Youwillhearatelephoneconversation.•Foreachquestion
最新回复
(
0
)