首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
admin
2019-01-16
60
问题
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
选项
答案
假定待排序的记录有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
学硕统考专业
相关试题推荐
下列城市：①南京②厦门③天津④杭州，按其在近代历史上开放为商埠的时间先后顺序排列应该是()
简述中共八大的内容以及主要历史功绩。
阅读材料，回答以下问题：一、大清帝国之皇统，万世不易。二、皇帝神圣，不可侵犯。三、皇帝权以宪法规定为限。四、皇帝继承之顺序，于宪法规定之。五、宪法由资政院起草议决，皇帝颁布之。六、宪政改正提案权，属于国会。七、上院议员，由国民于法定特别资格公选之。八、总
两汉时期，下列没有通过丝绸之路传入西方的技术是()。
简述雅典民主政治的形成过程、主要内容和历史局限性。
1923年纳粹党魁希特勒发动了“啤酒馆暴动”，对此叙述不正确的一项是()。
三国时期，魏、蜀、吴三国灭亡的历史顺序是()。
电子计算机的发展经过了：①电子数值积分计算机(ENIAC)②集成电路计算机③大规模集成电路汁算机④晶体管计算机⑤人工智能计算机其先后顺序是()。
标志着整风运动开始向反“右派”斗争转变的重要文件是()。
随机试题
下列关于B／S架构模式的叙述不正确的是
下列年轻恒牙龋病治疗的原则正确的是
具有保护胃粘膜作用的药物是
A、B两栋相同的住宅项目，总建筑面积86000㎡。施工时分A、B分区，项目经理下分设2名栋号经理，每人负责一个分区，每个分区又安排了一名专职安全员。项目经理认为，由栋号经理负责每个栋号的安全生产，自己就可以不问安全的事了。A区地下一层结构施工时，业
2012年11月1日，甲公司将2009年1月1日购入的乙公司于2008年1月1日发行的面值为500000元、期限为5年、票面年利率为5％、每年12月31日付息的债券的20％对外出售。实际收到价款105300元。由于该债券距离到期日只有两个月，剩余的乙公司债
消费者物价指数是指一组与居民生活有关的商品价格的变化幅度，生产者物价指数是指一组出厂产品批发价格的变化幅度。()
Y股份有限公司(以下简称Y公司)为A股上市公司。Y公司日常交易采用自动化信息系统(以下简称系统)和手工控制相结合的方式进行。系统自2011年以来没有发生变化。甲和乙注册会计师负责审计Y公司2013年度财务报表，Y公司2012年度财务报表也是由甲和乙注
下列人物中，既是诗人也是画家的是()。
以下有关选拔官员的方式与主要依据与“察举制——九品中正制——科举制”搭配正确的是（）。
Howmenfirstlearnedtoinventwordsisunknown;【B1】______,theoriginoflanguageisamystery.Allwereallyknowisthatme
最新回复
(
0
)
