首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
admin
2019-01-16
46
问题
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
选项
答案
假定待排序的记录有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://jikaoti.com/ti/9jfjFFFM
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
新文化运动把斗争矛头指向了儒家传统道德，是因为()
《关于建国以来党的若干历史问题的决议》
中国共产党领导下的民族区域自治模式最早是在()。
中华人民共和国恢复在联合国合法席位的时间是()。
第一个五年计划的具体时间段是()。
新中国成立初期的土地政策与解放战争时期的土地政策的主要区别是()。
简述按照恩格斯的划分方法人类的起源与进化。
西周的官僚制度已经相当完备，官僚机构庞杂，职官名目繁多。周王室的官僚机构分为两大系统，分别是()。
战国初期，上党地区在下列哪一个国家的控制范围之内（）。
(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，
随机试题
张余生前有两个儿子和一个女儿。他的大儿子生活比较好，但是不孝顺，对张余不管不顾。女儿远嫁他乡，生活上不方便照顾张余。张余与二儿子一起生活，二儿子也很照顾张余。张余没有其他继承人。张余去世后，遗产应该如何分割?()
以下所得，应按“工资、薪金所得”缴纳个人所得税的有()。
指数平滑预测法中，当α取值接近于0时，t+1期的预测值接近于()。
材料：访《蚁族》廉思“蚁族”群体多为“80后”，接受过高等教育
已知集合A={a，a+b，a+2b}，B={a，ac，ac2}，若A=B，求c。
【2015江西真题】学生对自己认知过程的认知策略称为学习的()。
农业科技人员向农民建议，在利用温室生产时，可向温室里施放适量的二氧化碳(CO2)．这是因为()。
依据制笔的原料不同，可以将毛笔分为羊毫笔、狼毫笔、紫毫笔、兼毫笔几种。其中，狼毫笔和紫毫笔的原料分别取自什么动物?()
A.itsdeepmeaninganditssimplicityB.oneoftheworstorationsC.nineminutesD.aperfectexampleoftherichoratoryof
Americansarenowsuper-sized,overweight,andfattyeven.ThisistrueofalmosttwothirdsofAmericanadults.Butwhatismor
最新回复
(
0
)
