首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
admin
2019-01-16
66
问题
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
选项
答案
假定待排序的记录有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/viRi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
进入20世纪50年代中期以后，雅尔塔体系演变的特点是()
中国共产党领导下的民族区域自治模式最早是在()。
陈云在哪次会议上发表了《目前财政经济的情况和克服困难的若干办法》的重要讲话?()
阅读以下史料，并回答问题：“为政以德，譬如北辰，居其所而众星共之。”“富与贵，是人之所欲也。不以其道得之，不处也。贫与贱，是人之所恶也。不以其道得之，不去也。君子去仁，恶乎成名?君子无终食之间违仁，造次必于是，颠沛必于是。”问题：对这一思想家的思
下列关于20世纪历史的叙述，全部错误的是()。①朝鲜建国的时间早于中国②1948年3月，英国、法网、比利时、荷兰、卢森堡5国缔结了《合作和集体防御条约》即《五国和约》③1950年，周恩来到达莫斯科，中苏缔结了《中苏互不侵犯条约》，标志着社会主义阵
1908年安庆新军起义是由()领导的。
马克思和恩格斯之所以能创立科学社会主义理论，主要是由于()。
假设系统的所有资源是同类型的，系统中的进程每次申请资源数最多1个，那么，下面列出的4种情况中，()可能发生死锁。情况序号系统中进程数资源总量
编写判定给定的二叉树是否是二叉排序树的函数。
既考虑作业等待时间又考虑作业执行时间的调度算法是()。
随机试题
某施工单位中标一座铁路大桥(施工范围不含图中阴影部分)，该桥跨越某三级通航河流，主跨为下承式钢梁，架桥机运梁车均可以在上面行驶。边跨为32m简支T形梁，要求现场制梁，采用公铁两用架桥机架梁，工期要求20个月，孔跨布置详见下图。问题：简述边跨梁部工程
关于良性黏膜类天疱疮的描述，不正确的是
目前最可能的诊断为该病人目前最需要的治疗是
关于脑膜瘤的影像表现，哪项描述不正确
无痛技术的局部麻醉方法主要包括
根据《建设工程设备招标投标管理试行办法》规定，投标需要有投标文件。下列属于投标文件基本内容的是()。
我们通常所说的统计数据包括()。
当前，一些地方的“美好乡村”建设，比较注重文化硬件设施，如文化墙、广场、体育设施等，但文化软件建设投入不够，比如先进文化素材的挖掘整理、好人好事的宣传教育、提升村民文化素养的引导等。重视文化软件建设，是因为()。①先进文化可以为人们认识和
完成某项具体学习任务所需要的时间与该项任务的动机水平成正相关。()
WhathashappenedsincetheandoftheIceAge?
最新回复
(
0
)
