首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
admin
2019-01-16
64
问题
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
选项
答案
假定待排序的记录有n个。由于含n个记录的序列可能出现的状态有n!个，则描述n个记录排序过程的判定树必须有n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没有分辨出来。我们知道，若二又树高度是h，则叶子结点个数最多为2
h-1
；反之，若有u个叶子结点，则二叉树的高度至少为(log
2
u)+1。这就是说，描述n个记录排序的判定树必定存在一条长度为log
2
(n!)的路径。即任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少是log
2
(n!)。根据斯特林公式，有log
2
(n!)=O(nlog
2
n)。即借助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为O(nlog
2
n)。 提示：此题考查的知识点是基于比较的排序算法效率。
解析
转载请注明原文地址:https://kaotiyun.com/show/viRi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
陈云在哪次会议上发表了《目前财政经济的情况和克服困难的若干办法》的重要讲话?()
阅读材料，回答以下问题：一、大清帝国之皇统，万世不易。二、皇帝神圣，不可侵犯。三、皇帝权以宪法规定为限。四、皇帝继承之顺序，于宪法规定之。五、宪法由资政院起草议决，皇帝颁布之。六、宪政改正提案权，属于国会。七、上院议员，由国民于法定特别资格公选之。八、总
两汉时期，下列没有通过丝绸之路传入西方的技术是()。
冶铁技术中的淬火法提高了铁器的坚韧与锋利程度，这一技术最早出现在()。
19世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。
三国时期，魏、蜀、吴三国灭亡的历史顺序是()。
下列哪一个不是罗马王政时代的管理机构?()
全国高校院系调整的具体时间是()。
17世纪英国资产阶级革命中，曾利用了古老文件同专制王权作斗争，这一古老文件是（）。
马克思和恩格斯之所以能创立科学社会主义理论，主要是由于()。
随机试题
慢性胃炎的主要确诊依据是
关于关节韧带描述，正确的是
老年人牙本质和牙髓结构的变化不包括
中阳衰微，胃有寒湿者忌用的药物是
A．异烟肼B．特比萘芬C．诺氟沙星D．氟胞嘧啶E．乙胺丁醇与铜离子形成红色螯合物()
与施工总承包模式相比较，施工平行发承包模式的优点有()。
一次性抚恤金是指国家按照军人死亡的性质，以货币形式给予其遗属的一次性物质抚慰。除工资低于排职少尉军官者，其发放标准以( )为基数，根据死亡性质分别乘以80、40或20，一次性发给其遗属。
初二学生李阳最近沉迷于电子游戏，经常无心上课，上课时精神萎靡不振，逃课现象严重，作业迟交或不交。班主任徐老师在屡次说教无果之后，改用上课时间罚站、罚跑、留校等方式进行惩罚。学校领导考虑到将来的升学率，将其从学校重点班级调回到普通班级。调回到普通班级以后，李
下列选项中属于附义务的行政许可的是（）。
Thespeakersaysitisnecessarytotalkabouthaybecause
最新回复
(
0
)
