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

admin2014-01-13 80

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

选项

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

解析

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

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

计算机专业知识

事业单位考试

相关试题推荐

随机试题

最新回复(0)

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

计算机专业知识

事业单位考试

“2013年中国好书”包括《繁花》《带灯》《中国经济双重转型之路》《3D打印：从想象到现实》等，其中《带灯》呈现了中国乡土社会在时代转型中复杂而尴尬的处境，小说中“带灯”是指()。

下列关于教育投资的说法，错误的是()。

被誉为“中国17世纪的工艺百科全书”，系统科学总结了16世纪末、17世纪中叶的农业和手工业生产技术的著作是()。

【2013年淄博市属文昌湖区真题】教育与生产力的关系叙述不正确的是()。

魏巍在《我的老师》一文中提到：“我们见了她(蔡老师)不由得就围了上去。即使她写字的时候，我们也默默地看着她，连她握笔的姿势都急于模仿。”这一叙述体现了学生的()特点。

课程标准是各学科的纲领性指导文件，它从整体上规定某门课程的性质及其在课程体系中的地位，规范性确定学科教学目标、内容范围、顺序，是教师教学工作的指南，是编写教科书和测评教学质量的依据。()

根据移动过程中所需的内在心理机制的不同，迁移可分为()。

Itwassuggestedthatthishardworkinggirl_______anexampleforotherstudents.

五更泄泻，腹痛喜温喜按，形瘦食少，神疲乏力，畏寒肢冷，舌淡者，多因

功能滋肾补肝，退虚热，明目的中药是

临床上常用于防治心律失常的药物组合是

上市公司增发新股过程的信息披露包括()。

当市场保持上升或下降趋势时，投资组合保险策略支付图为()

企业为特定客户设计产品所发生的可直接确定的设计费用应计入相关产品的成本。()

将50只鸽子分别放养在10个笼子里，且使得每个笼子里的鸽子的数目不同，则：

A．条件(1)充分，但条件(2)不充分．B．条件(2)充分，但条件(1)不充分．C．条件(1)和(2)单独都不充分，但条件(1)和条件(2)联合起来充分．D．条件(1)充分，条件(2)也充分．E．条件(1)和(2)单独都不充分，条件(1)和条件(2

Excel中，能够反映数据的变动情况及变化趋势的是()