首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
利用比较的方法进行排序,在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
利用比较的方法进行排序,在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
admin
2019-01-16
53
问题
利用比较的方法进行排序,在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
选项
答案
假定待排序的记录有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
学硕统考专业
相关试题推荐
宋代由于旧坊制被打破,城市中行业分区性逐渐消失,北宋政府通过()来控制商人和商业。
“两个凡是”
简述中共八大的内容以及主要历史功绩。
论述宋初加强中央集权的主要措施。
拜占庭帝国的第二个黄金时代是在()。
在“冷战”形成的过程中,影响苏联领导人对美政策变化的关键性事件是()。
下列哪些机构是唐朝设立的管理新疆地区的机构?()①伊犁将军②乌里雅苏台将军③北庭都护府④安西都护府
列宁在《四月提纲》中指出,俄国的革命任务是()。
武则天时期,为了管理天山以北的广大区域而设立了()。
20世纪50年代到70年代初,西欧国家通过有效的社会经济政策,维持了经济相对稳定和持续发展。这些政策主要包括()①加强对经济的宏观管理②废除生产关系中封建落后因素③发展高科技和新兴产业④进行社会改革,稳定社会
随机试题
“信息符合时效性要求,内容不过时”是指信息的()
慢性肺心病患者死亡的首要原因是
Grey-Tumer征是指
关于寻衅滋事罪,下列说法正确的有()。
房地产开发企业在计算企业所得税应纳税所得额时,下列处理方法不正确的是()。
危机是否能够解决,最终取决于()。
在教育理论研究过程中,第一个基本步骤是()
法院在接到起诉状时对符合规定的起诉条件的,应当登记立案。()
以权利的相互关系为标准,民事权利可以分为()。
"Fossilization"isanimportantcharacteristicofthe
最新回复
(
0
)