首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
admin
2019-08-15
56
问题
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
选项
答案
假定待排序的记录有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/jKCi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一，为重新认识三代的历史与文化奠定了基础，开辟了坦途，可称之为中国文化史的里程碑。根据所学知识回答问题：下列有关“甲骨文”的表述，不确切的是()
《中国国民党改组宣言》发表的时间是()。
从“鲁尔危机”的发生到《道威斯计划》的实施，西方国际关系变化对当时有关国家的影响是()。①美国势力进一步向欧洲渗透②英国达到了限制法国、保持均势的目的③德国获得重建经济的有利时机④法国扩充实力争霸欧洲的计划遭
唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落，而且对后来的历史产生了严重影响。据此回答问题后晋一个节度使说：“天子宁有种耶?兵强马壮者为之!”这说明五代十国分裂局面的实质是()
19世纪曾形成了以()为中心的资本主义世界经济体系；二战后，逐渐形成了以()为中心的资本主义世界经济体系。
米勒兰事件
在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。
某计算机有8个主设备需要竞争总线的使用权，其设备号为0～7。现欲设计其判优控制方法，试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制，则在链式查询、计数器定时查询和独立请求三种方式下，
有一个仓库，可以存放A和B两种产品，但要求：(1)每次只能存入一种产品(A或B)；(2)-N＜A产品的数量-B产品的数量＜M。其中，N和M是正整数。试用P，V操作描述产品A与产品B的入库过程。
某一个计算机系统采用虚拟页式存储管理方式，当前在处理机上执行的某一个进程的页表如下所示，所有的数字均为十进制，每一项的起始编号是0，并且所有的地址均按字节计址，每页的大小为1024字节。(1)计算下列逻辑地址转换为物理地址，并说明为什么
随机试题
左图为给定的多面体，从任一角度观看，下面哪一项不可能是该多面体的视图?
ACTH是指
某道路工程的边坡主要为易受雨水冲刷的土质边坡和易风化的岩石边坡，对这些边坡进行防护最适用的方法是()。
一般会计人员在会计工作交接时，负责监交的是()。
教育的个体功能要转化成政治、经济功能，是通过提高人口素质来实现的。教育的人口功能体现为()。
有民事行为能力的公民在被宣告死亡期间实施的民事法律行为有效。（）
如果决策者们不是受外界的影响去追求“完美”的解决问题的办法，而是限制自己的探索，发现满意的答案即可，那他们就能节省大量的精力。这段话所表达的观点是（）。
在一辆客车突然失控并冲向学生的危急时刻，张丽莉老师不顾个人的生命安危，挺身而出，为抢救两名学生而被卷入车下遭到碾压，以至双腿高位截肢。把生的希望留给学生，把死的危险留给自己，以自己的柔弱身躯支撑起一片生命的天空，用行动谱写了一曲感天动地的大爱赞歌。“最美教
设函数y=y(x)由e2x+y-cosxy=e-1确定，则曲线y=y(x)在x=0对应点处的法线方程为______
WhenHarvardstudentMarkZuckerberglaunchedthefacebook.cominFeb.2004,evenhecouldnotimaginetheforcesitwouldlet
最新回复
(
0
)
