首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
admin
2017-11-14
87
问题
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
选项
答案
假定待排序的记录有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
学硕统考专业
相关试题推荐
1956年，苏共二十大后，匈牙利大党员和群众强烈要求克服个人崇拜，扩大民主，实行经济改革，一些由知识分子、大学生和干部组成的社团组织纷纷成立，其中最有影响者是()。
近代天文学革命引起教会人士的极端仇恨，其根本原因是它()
关于希腊早期宗教的叙述不正确的是()。
美国工业革命的有利条件包括()。①美国自然资源丰富②独立战争后，美国创立了资产阶级共和制度③地理位置优越，远离动乱的欧洲④拥有潜在的广阔的国内市场
解放军渡江战役中横渡长江的东西两个攻击点是()。
全国高校院系调整的具体时间是()。
阅读下列材料，回答问题：材料一：列宁说：“我们在夺取政权时便知道，不存在将资本主义制度具体改造成社会主义制度的现存方法……我不知道哪位社会主义者处理过这类问题……我们必须根据实践作出判断。”——摘自《苏联
晚清时期清帝年号的正确排序是
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令，平均每条指令需要5个机器周期，其中3个周期必须访问内存，内存读写需一个机器周期，假定CPU在95％的时间内持续执行“背景程序”，且这段时间内不执行I／O指令。现
采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51；(1)构造散列表(画示意图)；(2)装填因子；(3)等概
随机试题
我国成立的第一个民族区域自治的县级自治区是()
下列关于掠夺性定价行为的表述中，不正确的是()
某男，40岁，腹胀、腹部持续性隐痛、发热一周。“肝炎”史12年，近4年来乏力、纳差，面色晦暗，间断性齿龈出血。查体：腹部膨隆，无肌紧张，全腹压痛及反跳痛，肝肋下未触及，脾肋下3cm，移动性浊音阳性。为明确诊断，最有价值的检查是()
关于Ⅲ度烧伤，下列说法正确的是()。
某地基工程公司2015年度共实现利润总额2400万元，所得税费用500万元，根据企业会计准则及其相关规定，该公司当期净利润应为()。
以下不属于独立董事主要职责的是()。
甲公司20×4年1月1日购入乙公司当日发行的一笔一次还本付息的债券，面值为1000万元。该债券为5年期债券，票面利率为7％，假定实际利率为3％，甲公司支付购买价款1164．51万元。甲公司将其划分为持有至到期投资。20×4年年末，该债券出现减值迹象，预计未
USUniversity【D1】______Exams:A.SATAcombinationofhighschoolgradesandSATscoresisbelievedtobe【D2】______offreshm
A、Aplatformworker.B、Thecommandspot.C、Acomputer.D、Amachine.D事实细节题。短文中指出，在“维多利亚线”上，是机器在进行检票和回收车票的工作，站台上一个工作人员都没有。
A、2yearsold.B、3yearsold.C、4yearsold.D、8yearsold.D选项都是岁数，这些数字可能在原文中都出现过，这就要求在听录音的同时，听到每一个数字都要在旁边做笔记。原文两次提到，直到8岁时儿童的某只
最新回复
(
0
)
