首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
公务员
利用比较的方法进行排序,在最坏情况下,能达到的最好时间复杂度是多少?请给出详细证明。
利用比较的方法进行排序,在最坏情况下,能达到的最好时间复杂度是多少?请给出详细证明。
admin
2014-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
最新回复
(
0
)