首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
admin
2019-01-16
31
问题
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
选项
答案
假定待排序的记录有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/glRi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列不属于“一国两制”的基本内容的是()。
简述中共八大的内容以及主要历史功绩。
下列哪个文件标志着“文化大革命”的发起?()
论述宋初加强中央集权的主要措施。
阅读材料，回答以下问题：一、大清帝国之皇统，万世不易。二、皇帝神圣，不可侵犯。三、皇帝权以宪法规定为限。四、皇帝继承之顺序，于宪法规定之。五、宪法由资政院起草议决，皇帝颁布之。六、宪政改正提案权，属于国会。七、上院议员，由国民于法定特别资格公选之。八、总
8世纪利用汉字偏旁创造日本片假名的是()。
在意大利统一过程中，加富尔为了获得拿破仑三世的支持，让与法国的领土是()。
19世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。
某计算机有五级中断L4～L0，中断屏蔽字为M4M3M2M1M0，Mi=1(0≤i≤4)表示对Li级中断进行屏蔽。若中断响应优先级从高到低的顺序是L4→L0→L2→L1→L3，则L1的中断处理程序中设置的中断屏蔽字是____。
随机试题
战略实施
每克脂肪提供热量
下列哪项不是寒凉药性所表示的作用（）
下列有关应付票据处理的表述中，正确的有()。
根据《刑事诉讼法》第16条的规定，对于享有外交特权和豁免权的外国人犯罪应当追究刑事责任的，通过()解决。
在最近的战争中，在一场激烈的战斗中执行任务的医疗人员，即使是那些免受身体伤害的，比起那些在这场战争中执行不太激烈的战斗任务的医疗人员，现在都显得收入较低而离婚率较高，而且在关于总体幸福感的心理状况测量中得分也较低。这一证据证明：即使是那些没有受到身体伤害的
对计算机网络发展具有重要影响的广域网是
下面描述中，不属于软件危机表现的是( )。
Ifsomeoneissleepwalking,theyarewalkingaroundwhiletheyareasleep.Sleepwalkinghappenswhenapersonisnotfullyaslee
Yelloworpinkflowers?Thegreenorbluesweater?Wemakedecisionsaboutcolorallthetime.Now,scientistsarestartingtof
最新回复
(
0
)
