首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
利用比较的方法进行排序,在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
利用比较的方法进行排序,在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
admin
2019-01-16
84
问题
利用比较的方法进行排序,在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
选项
答案
假定待排序的记录有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/viRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
解放军渡江战役中横渡长江的东西两个攻击点是()。
()是中国历史上第一次大规模的群众性武装暴动。
春秋战国时期,提出“祸兮福之所倚,福兮祸之所伏”的思想家是()。
阅读材料,回答以下问题:一、大清帝国之皇统,万世不易。二、皇帝神圣,不可侵犯。三、皇帝权以宪法规定为限。四、皇帝继承之顺序,于宪法规定之。五、宪法由资政院起草议决,皇帝颁布之。六、宪政改正提案权,属于国会。七、上院议员,由国民于法定特别资格公选之。八、总
下列哪些机构是唐朝设立的管理新疆地区的机构?()①伊犁将军②乌里雅苏台将军③北庭都护府④安西都护府
三国时期,魏、蜀、吴三国灭亡的历史顺序是()。
清廷实行厘金制度的时间是()。
系统地阐明道家思想的著作《淮南鸿烈》,也叫《淮南子》,是汉武帝时()集宾客写成的。《淮南子》问世时,黄老思想在政治上已不占支配地位了。
唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落,而且对后来的历史产生了严重影响。据此回答问题当代史学界认为安禄山、史思明反唐是一场叛乱,其基本理由是他们()
某计算机采用微程序控制方式,微指令字长32位,采用字段直接编码的控制方式,共有55个微命令,可分为6个互斥组,分别包含1、3、7、8、12、24个微命令。另外,该机共有5个可判定的外部条件,采用断定方式形成后续微指令地址。(1)设计该机微指令的格式,
随机试题
周任有言曰:“_____________,_____________。”《论语﹒季氏将伐颛臾》
患者,男性,37岁,1年来每日发生空腹痛,进食后疼痛缓解。平时伴有恶心、打嗝、反酸,查体在剑突右侧有局限压痛,无反跳痛。目前认为该病是何种细菌感染引起
拓海公司系私营独资企业,因欠债被诉诸法院,后被判令履行金钱给付义务。履行期限届满后,拓海公司仍未还债。经债权人申请,人民法院对其予以强制执行。经查,该公司无偿还能力。在下列后续措施中何种是正确的?
完全无风险的投资在现实中难以找到,对此可选用同一时期的一年定期存款法定利率(或一年国债利率)去代替安全利率。于是()。
按建标[2003]206号文规定,教育费附加的计费基础是( )。
工作环境中引起疲劳最客观、最直接的因素有()。
2015年1—6月民间固定资产投资154438亿元,占全国固定资产投资的比重为65.1%,比1—5月下降0.3个百分点。分产业看,2015年1—6月第一产业民间固定资产投资4992亿元,同比增长31.4%;第二产业77298亿元,增长10
材料:下面是某初中生物教师编制的客观题试题:一、单项选择题①植物根部通过根毛吸收而来的水分和无机盐进入植物体内后通过()运送到植物的枝、叶、花和果实。A.导管B.筛管C.细胞间质②植物的繁殖器官是()。A.根、茎、叶B
马克思主义产生的经济社会条件是
A、Thetrainiscrowded.B、Thetrainislate.C、Thetrainisempty.D、Thetraifiisontime.B由男士话中可知火车晚点(Thetrainisbehindsch
最新回复
(
0
)