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

admin2014-01-13 35

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

选项

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

解析

转载请注明原文地址:https://jikaoti.com/ti/B7U3FFFM

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

计算机专业知识

事业单位考试

相关试题推荐

随机试题

最新回复(0)

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

计算机专业知识

事业单位考试

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

宋老师发现了教学中的某一问题并对其描述，继而形成解决计划并实施，随后搜集数据和材料以分析计划的有效性，最后把结果应用于处理后续课堂中出现的类似问题。这种研究的方法是()。

尊重的需要在马斯洛的需要层次理论中属于()。

以下关于职业道德说法错误的是()。

不同的教学班，有不同的群体规范，不同的凝聚方式。对于已经形成了良好的学风和群体规范而且有较强凝聚力的班级，教师不宜采用的课堂管理方式是()。

智商也叫智力商数，常用IQ表示，计算智商的公式为()。

课程标准是课程计划中每门学科以纲要的形式编写的，是有关学科教学内容的指导性文件。()

在Word中，()用于控制文档在屏幕上的显示大小。

从第一代计算机到第四代计算机的体系结构部是相同的。这种体系结构称为（）体系结构。

故意把事物往大处说，叫_____夸张。

肉及其制品的水分含量与其中微生物的生长发育有关，国家标准中规定肉干、肉松制品中水分的质量分数应小于()。

左心房血栓脱落不会引起：

下列选项中，环境风险的防范、减缓措施有()。

沥青混合料按材料组成及结构划分可分为（）与间断级配混合料。

在营运资金管理中，企业将“产品卖出后到收到顾客支付的货款的这一时间段”称为()。

我国古典军事思想中，有“围魏救赵”“声东击西”之说；在古典文学中，形容一个人表里不一，也有“佛面兽心”之说。针对以上观点下列表述错误的有()

在过程定义中有语句：PrivateSubGetData(ByReffAsInteger)其中“ByRef”的含义是

WorkshoptoFocusonGrantProcessLauraChinwillpresentaworkshopThursdayshowingnonprofitgroupshowtoapplyforNei

Whatdodietingandenergypolicyhaveincommon?TheSnackWelleffect.Thenamecomesfromthosetastylittlecookiesthatare【