首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
利用比较的方法进行排序,在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
利用比较的方法进行排序,在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
admin
2019-08-01
72
问题
利用比较的方法进行排序,在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
选项
答案
假定待排序的记录有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/3ACi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
阅读材料并结合背景知识回答问题:材料到17世纪60年代,伟大的科学学会的时代到来了:英国皇家学会、法国科学院先后成立。此前,科学工作在很大程度上仰仗于国王对科学家个人的资助一第谷领取丹麦国王的津贴,开普勒由德意志皇帝资助;或者靠某些科学“爱好者”、赞助者
罗马法的集大成《查士丁尼民法大全》产生的时间是在()。
完整地表述电磁场理论的物理学家是()。
二次大战后,主要资本主义国家经历了增长时期,首先开始这个进程的国家是()。
下列不属于苏联高度集中的经济政治体制产生的条件的是()。
根据1931年的威斯敏斯特法,英国()。
在1875年宪法中关于法国立法权的叙述,不正确的是()。
关于清代我国疆域的叙述,下列()不正确。
新文化运动前期的指导思想是()。
对三国鼎立局面的形成起到关键性作用的战役是()。
随机试题
两个以上污染者污染环境造成他人损害的,污染者承担
血清促胃液素增高伴胃酸缺乏的是
机体各种功能活动所消耗的能量中,最终不能转化为体热的是
下列哪项疾病的临床症状一般不是外阴瘙痒
三叉神经痛的药物治疗最有效的是
最好与铁剂同时服用的药物是
重力式挡土墙断面如图,墙基底倾角为6°,墙背面与竖直方向夹角20°。用库仑土压力理论计算得到每延米的总主动压力为Ea=200kN/m,墙体每延米自重300kN/m,墙底与地基土间摩擦系数为0.33,墙背面与填土间摩擦角15°。计算该重力式挡土墙的抗滑稳定安
《建设工程质量管理条例》规定,施工单位必须按照工程设计要求、施工技术标准和合同约定,对()进行检验,检验应当有书面记录和专人签字;未经检验或者检验不合格的,不得使用。
某房地产开发企业拟开发建设一个由十幢住宅、一幢幼儿园和一幢物业服务中心组成的住宅小区。该住宅小区包括()。
数据库恢复属于商品流通企业数据库管理系统功能中()功能。
最新回复
(
0
)