首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
admin
2019-08-01
53
问题
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
选项
答案
假定待排序的记录有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年代，伟大的科学学会的时代到来了：英国皇家学会、法国科学院先后成立。此前，科学工作在很大程度上仰仗于国王对科学家个人的资助一第谷领取丹麦国王的津贴，开普勒由德意志皇帝资助；或者靠某些科学“爱好者”、赞助者
印度列国时代出现了16个国家，其中大部分是王国，只有少数的共和国。下列属于共和国的是()。
苏联“十四大”“十五大”后经济建设的核心内容是()
以下不属于泰州学派的哲学思想的是()。
到1869年为止，人类已发现了多少种化学元素()。
评述马基雅维利的政治思想。
汉建武二十四年(公元48年)匈奴()被南边八部拥立为南单于，他袭用其祖父呼韩邪单于的称号，请求内附，得到东汉的允许。从此以后，匈奴分裂为南北二部。
提出电磁感应定律的是物理学家()。
已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列
随机试题
烃类是由碳和()两种元素所组成的一类有机化合物，主要来源于天然气、石油和煤的加工产物。
简述行政相对人在程序法上的权利。
妊娠腹痛的特点是
A、硫酸铁铵B、结晶紫C、淀粉D、二甲酚橙E、酚酞；下列测定中所选择的指示剂为用HClO4滴定液测定盐酸麻黄碱
在一起共同犯罪案件中，主犯王某被判处有期徒刑十五年，剥夺政治权利三年，并处没收个人财产；主犯朱某被判处有期徒刑十年，剥夺政治权利二年，罚金2万元人民币；从犯李某被判处有期徒刑八个月；从犯周某被判处管制一年，剥夺政治权利一年。(2008—卷二—95～97，任
甲想加入乙、丙为合伙人的普通合伙企业，下列各项中，不属于甲在入伙时必须满足的条件是()。
材料：美国心理学家罗森塔尔考查某校，随意从每班抽3名学生共18人写在一张表格上，交给校长，极为认真地说：“这18名学生经过科学测定全都是智商型人才。”事过半年，罗森塔尔又来到该校，发现这18名学生的确超过一般，长进很大，再后来这18人全都在不同的岗位上干
对学习过程中制定自我学习计划，实施自我监督以及自我调控的策略，一般称为()
根据下列统计资料回答问题。生物多样性是人类社会赖以生存和发展的基础。我们的衣、食、住、行及物质文化生活的许多方面都与生物多样性的维持密切相关。由于自然资源的合理利用和生态环境的保护是人类实现可持续发展的基础，因此生物多样性的研究和保护已经成为世界
绝对真理和相对真理是辩证统一的关系。将二者的关系割裂会导致的错误有()
最新回复
(
0
)
