首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
利用比较的方法进行排序,在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
利用比较的方法进行排序,在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
admin
2017-11-14
86
问题
利用比较的方法进行排序,在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
选项
答案
假定待排序的记录有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
学硕统考专业
相关试题推荐
晚清时期清帝年号的正确排序是()
“我不想变成上帝,或居住在永恒之中,或者把天地抱在怀里,属于人的那种光荣对我就够了。我自己是凡人,我只要求凡人的幸福。”这句话体现的思想是()
毛泽东明确提出“中国革命斗争的胜利要靠中国同志了解中国情况”论断的著作是()。
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
陈云在哪次会议上发表了《目前财政经济的情况和克服困难的若干办法》的重要讲话?()
下列不属于延安整风运动的文件是()。
世界天文史上最早实地测量子午线的记录是由谁进行的?()
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
在下列排序方法中不需要对排序码进行比较就能进行排序的是()。
随机试题
一位有机磷重度中毒患者,经2天治疗,症状已缓解,治疗上可以
治疗A组溶血性链球菌用MRSE和MRSA败血症选用
精气生万物的机理是天地阴阳二气的
按房地产开发资金的占用形态划分,库存设备、材料等占用的资金属于()
已知甲、乙两个方案为互斥方案,且两个方案计算期相同。已知NPV(甲)=186.46元,NPV(乙)=132.95万元,那么应选择()。
教学从本质上说,是一种()。
请开始答题:2789
Humaningenuitywasinitiallydemonstratedin______.Theauthorusestheexampleofamonkeytoarguethatrobotsare______.
拨号连网,不需要______设备。
Singaporeiswellknownasamulti-racial,multi-culturalandmulti-religiousnation.Andthis【C1】______isgraduallybecoming
最新回复
(
0
)