首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
admin
2019-01-16
85
问题
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
选项
答案
假定待排序的记录有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/viRi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
()是中国历史上第一次大规模的群众性武装暴动。
试论春秋战国时期思想文化获得发展的主要原因。
阅读以下史料，并回答问题：“为政以德，譬如北辰，居其所而众星共之。”“富与贵，是人之所欲也。不以其道得之，不处也。贫与贱，是人之所恶也。不以其道得之，不去也。君子去仁，恶乎成名?君子无终食之间违仁，造次必于是，颠沛必于是。”问题：对这一思想家的思
简述路德“唯信称义”与加尔文“预定论”的关系与区别。
西周统治者提出的天命思想和与此相应的治国思想分别为()。
阅读下列材料，并结合所学知识回答问题：材料一重申粮食垄断和价格都是不可更改的，重申必须同粮食投机商进行无情斗争，同时责成每一者，必须在本法令公布后一周内，把超过播种田地和自己到下次收获前的定额消费量的全部余粮呈报交售，呈报的办法由粮
16世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。
()时，为补充兵力，开拓财源，“料民于太原”(今山西西南部)。料民就是清查民数，以便于征兵，结果引起奴隶和平民的反抗。这表明西周王朝已失去了对社会的控制力量。
IP数据报的报文格式如下图所示。在没有选项和填充的情况下，报头长度域的值为()。
试编写一个非递归算法，实现求以二叉链表存储的二叉树中q结点的祖先。
随机试题
下列有关风湿病的描述，错误的是
十二经脉气血流注，阴经和阳经的交接部位有
患者男，33岁，尿频、尿痛2天入院。查体：尿道外口有脓性分泌物，涂片见大量革兰阴性咖啡豆形双球菌。有关该病原菌的描述正确的是
产妇孙某，自然分娩，产后2h观察内容不包括（ ）。
诉讼时效与除斥期间的区别主要表现在()。
(2014年)参加基本医疗保险的职工的医疗费用依法应由第三人负担，但第三人不支付或者无法确定第三人的，由()先行支付。
计算企业所得税的应纳税所得额时,下列项目不属于应纳税所得额的是()。
下列项目中，应作为城市维护建设税计税依据的是()。
WhenIheardthenoiseinthenextroom,Icouldn’tresisthavinga(peep)look.
DearSir,IwillgraduatefromShanghaiUniversityofInternationalBusinessandEconomicsthisyear.Asastudentmajoring
最新回复
(
0
)
