首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
admin
2017-11-14
65
问题
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
选项
答案
假定待排序的记录有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://www.kaotiyun.com/show/W3Ri777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
【迈镊尼文明】东北师范大学1999年世界上古史真题
引发20世纪70年代资本主义世界最严重的一次经济危机的直接原因是()。
1956年，苏共二十大后，匈牙利大党员和群众强烈要求克服个人崇拜，扩大民主，实行经济改革，一些由知识分子、大学生和干部组成的社团组织纷纷成立，其中最有影响者是()。
武昌起义()。①由同盟会直接领导②原计划被偶然因素打乱③其成功有深刻的社会原因④迅速的胜利潜伏着失败的危机
“国际工人协会”宣布成立后，10月协会选出了第一任主席，他是()。
建立帝国财政收支总账和元首金库，直接控制和调节全国财政收支的是()。
简述按照恩格斯的划分方法人类的起源与进化。
德国纳粹党消灭资产阶级民主制的关键性事件是()。
美国首次提出争夺世界霸权的纲领性文件是()。
42．设有带头结点的循环双链表表示的线性表L=(a1，a2，……，an-1，an)。设计在时间和空间上都尽可能高效的算法，将L改造成L=(a1，a2，……，an，……a4，a2)。要求：(1)给出算法的基本设计思想。(2)根据设计思想，
随机试题
发行推广
为确诊，下列哪项检查最有价值在该患者进行结核菌试验，预计可能出现下列不同情况，哪一项解释是错误的
王某系来京务工人员，一日傍晚见到老乡开着一辆卡车停在工地旁，趁老乡下车，走过去发动，驾车离开公司，在某路段岔口硬闯红灯，躲闪不及，撞在迎面开来的一辆小面包车上，将司机甲当场撞死，乘客乙被撞成重伤，王某看到夜色已晚，悄悄把乙拉在草丛中，后乙失血过多、没有及时
建国以来,我国土地所有权制度进行的四次大调整是()。
初步统计，2003年我国全年全社会固定资产投资55118亿元，比上年增长26.7%，平均每月增加投资()亿元。
下列各项．不属于Windows窗口标题栏项目的是()。
下列哪个图形可以由左边给定的图形折出?()
OnesillyquestionIsimplycannottolerateis"Howdoyoufeel?"Usuallythequestionisaskedofamaninaction—amanwalking
在进行资本预算的过程中，计算项目的期间营运现金流量时，如果项目的部分资金来源于债务，那么需要在现金流中扣除利息费用，并按照WACC作为贴现率评估项目价值。()。
Somanypeopleusethecellphonesofrequentlyeveryday.But【C1】______littleiscertainaboutthehealtheffectsofitsuse.
最新回复
(
0
)
