首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
admin
2017-11-14
64
问题
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
选项
答案
假定待排序的记录有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/W3Ri777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
中国第一个资产阶级革命团体兴中会建立的时间是()。
陈云作《目前财政经济的情况和克服困难的若干办法》的重要讲话，分析当前财政经济方面的主要困难，提出克服困难的六点意见的会议是()。
西汉末年，()对太初历作了系统的解释，并调整为三统历。这是中国第一部记载完整的历法。
与前两次工业革命相比，第三次科技革命在能源结构上的主要变化是()
关于中世纪西欧城市发展状况，叙述正确的是()。①城市取得自由或自治，一般以赎买为手段。②城市的自由和自治，一般以封建主或国王颁发的特许证书为凭据。③有的城市集体为封君服军役，并履行封臣的其他义务。④城市可视为
战时共产主义政策中对后来的工农联盟最能构成威胁的是()。
在欧盟发展历史上，促使欧盟正式成立的文件是()。
中共八届九中全会提出的恢复和调整国民经济的方针是()。
1534年英国议会宣布英国教会断绝与罗马教廷一切关系的文件是()。
下列描述中，属于冯.诺依曼体系结构的特点是()。①采用流水线技术；②指令和数据均以二进制表示；③存储程序并且存储时不区别数据和指令。
随机试题
性激素属于
一般地表水处理厂采用的常规处理流程为()。
在全国银行间债券市场进行买断式回购，交易双方可以协商确定（ ）。
齐胜夫妻二人因为感情不和提出离婚，那么二人在诉讼离婚时必经的庭审程序是()。
关于臀中肌、臀小肌注射说法正确的是()。
股份制是现代企业的一种资本组织形式，但“不能笼统地说股份制是公有还是私有”，对这句话的正确理解是()。
阅读下文，回答下列几题：由于人脑的信息处理能力已经达到极限，因此人类永远不会变得比今天聪明得多。英国东部伊普斯威奇市的英国电信公司实验室的科学家称，由于人脑中神经元的大小和数量与为它们提供营养的血管之问存在微妙的平衡关系，因此根本的改善是不可能的
PopstarstodayenjoyastyleoflivingwhichwasoncetheprerogativeonlyRoyalty.Wherevertheygo,peopleturnoutinth
DoyouthinktheinformationfromsocialmediasuchasTwitterandFacebookisreliable?
Hisgreatest______ishisutterlynaturalandprofoundlygoodmusicalinstinct.
最新回复
(
0
)
