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

admin2014-01-13 36

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

选项

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

解析

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

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

计算机专业知识

事业单位考试

相关试题推荐

随机试题

最新回复(0)

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

计算机专业知识

事业单位考试

把课程编制分为确定教育目标、选择学习经验、组织学习经验、进行课程评价四大步骤，主张以教育目标为中心来编制学校课程的学者是()。

国务院根据宪法和法律制定的关于行政管理的规范性文件总称为()。

《国家中长期教育改革和发展规划纲要(2010——2020年)》提出的工作方针包括()。

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

习近平总书记指出中国社会发展必须拥有的自信有()。

在相关分析中，完全正相关的相关系数是()。

不考虑学生的年龄特征，在教育要求、教育教学内容和方法选择上的“一刀切”，违背了个体身心发展的()。

根据教育目的和不同类型学校的培养目标，由国家教育主管部门制定的有关学校教学和教育工作的指导性文件是()。

当前中国经济形有波动，势仍平稳，继续向好。我们要适度扩大总需求。以下所列有利于扩大总需求的措施有()。

班级既是几十个学生自愿组合的产物，也是学校为了便于管理和更好地开展教育、教学活动、实现教育目的而特地组织起来的，带有一定强制性的群体。()

交往动机

钢中含碳量的变化对力学性能有什么影响?

美国管理学家卡茨(RobertL．katz)认为，一个管理者至少拥有的三大基本技能是技术技能、概念技能和______。

面色赤与下列哪项病证有关

A、卡比多巴B、苯海索C、左旋多巴D、溴隐亭E、维生素B6青光眼、前列腺肥大者慎用

湖泊简化时，下列说法正确的是()。

预测性财务信息的审核不属于注册会计师的审计业务。（）

公安机关要建立()，通过治安信息的收集与分析，不断提高对治安危害的预见性，加强超前控制。

某次考试共有9题，做对第1～9题的人数分别占到参加考试总人数的82％、65％、92％、93％、68％、98％、70％、60％、72％，如果做对5道或5道以上为及格，则这次考试的及格率至少为：