首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
公务员
利用比较的方法进行排序,在最坏情况下,能达到的最好时间复杂度是多少?请给出详细证明。
利用比较的方法进行排序,在最坏情况下,能达到的最好时间复杂度是多少?请给出详细证明。
admin
2014-01-13
32
问题
利用比较的方法进行排序,在最坏情况下,能达到的最好时间复杂度是多少?请给出详细证明。
选项
答案
假定待排序的记录有n个。由于含n个记录的序列可能出现的状态有n!个,则描述n个记录排序过程的判定树必须有n!个叶子结点。因为若少一个叶子,则说明尚有两种状态没有分辨出来。若二叉树高度是h,则叶子结点个数最多为2h-1个;反之,若有u个叶子结点,则二叉树的高度至少有log2tl+1。这就是说,描述n个记录排序的判定树必定存在一条长度为Iog2(n!)的路径,即任何一个借助“比较”进行排序的算法,在最坏情况下所需进行的比较次数至少。根据斯特林公式,有lOg2(n!)=(nlg2r1),即借助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为(nlog2r1)。
解析
转载请注明原文地址:https://jikaoti.com/ti/B7U3FFFM
本试题收录于:
计算机专业知识题库事业单位考试分类
0
计算机专业知识
事业单位考试
相关试题推荐
在Windows系统中,若强行关闭一个正在运行的程序,可以使用任务管理器来结束它。打开任务管理器需按下()。
心理学家邓克尔设计了一个“蜡烛实验”。在桌子上有三个硬纸盒,盒里分别装着图钉、火柴和蜡烛。要求被试者用桌子上的这些物品将蜡烛固定在木纸墙上。解决钧方法很简单:把纸盒钉在墙上,再以它为台基竖立蜡烛。但许多被试者不会这样解决问题,因为他们把装着东西的纸盒当作容
《教育部关于加强和改进普通高中学生综合素质评价的意见(教基二(2014]11号)》规定了普通高中学生综合素质的评价内容,包括思想品德和()。
现代课程开发理论中的经典“泰勒原理”所回应的问题有()。
党的十八大强调,建设中国特色社会主义,总依据是社会主义初级阶段,总布局是五位一体,总任务是实现社会主义现代化和中华民族伟大复兴。以下不属于五位一体建设的是()。
加涅对人类学习进行了分类,用以代表个体所获得的所有学习结果。这些学习结果包括()。
学业评价是指根据测验分数、观察和报告,对被测验者的行为、作业的优点或价值作出()。
操作性条件反射与经典性条件反射的基本原理是相同的,他们都是随着强化的次数增加而巩固。由于未得到强化而消退。
材料1:蔡斯和西蒙(Chase&Simon,1973)对象棋大师、一级棋手和业余新手对棋局的记忆能力进行了研究。给他们5秒时间观看一盘中局对弈国际象棋棋盘布局。5秒后,把棋盘盖上,要求每位参与者尝试在另一棋盘上复现棋子位置。这一过程尝试多次,直到得到满意的
有如下嵌套的if语句:if(a
随机试题
Howmanymoredecadeswillhavetopass______scientistssucceedinprovidingacureforcancer?
目前常用的梅毒实验检查包括哪两大类?各有哪些主要实验?
紫苏不具有的功效是()
女,35岁。发作性头痛4年,部位不定,每次持续数小时至1天,发作前视物有模糊暗影,神经系统体检未见明显异常。脑CT未见异常,其母有类似发作史。头痛发作早期的首选药物是
A、哌替啶B、美沙酮C、芬太尼D、可待因E、喷他佐辛镇痛作用弱于吗啡,主要用于无痰剧烈干咳的是
关于Partnering模式的协议系统,说法不正确的是()。
雇佣合同能够进行自我强化的关键之处在于()。
下列各项资产和负债中,因账面价值与计税基础不一致形成暂时性差异的有()。
2,3,10,15,()
WhichofthefollowingmightfailtoassociateyouwithLondon?
最新回复
(
0
)