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