首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
公务员
利用比较的方法进行排序，在最坏情况下，能达到的最好时间复杂度是多少?请给出详细证明。
利用比较的方法进行排序，在最坏情况下，能达到的最好时间复杂度是多少?请给出详细证明。
admin
2013-12-19
78
问题
利用比较的方法进行排序，在最坏情况下，能达到的最好时间复杂度是多少?请给出详细证明。
选项
答案
假定特排序的记录有n个。由于含n个记录的序列可能出现的状态有n!个，则描述n个记录排序过程的判定树必须有n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没有分辨出来。若二叉树高度是h，则叶子结点个数最多为2
h-1
个；反之，若有u个叶子结点，则二叉树的高度至少有1og
2
u+1。这就是说，描述n个记录排序的判定树必定存在一条长度为1og
2
(n!)的路径，即任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少是log2(n!)次。根据斯特林公式，有log
2
(n!)=()(nlog
2
n)，即借助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为O(nlog
2
n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/aval777K
本试题收录于：
计算机专业知识题库事业单位考试分类
0
计算机专业知识
事业单位考试
相关试题推荐
以个人好恶、兴趣爱好为联系纽带，具有强烈情感色彩的群体是()。
不将学习主要内容直接呈现给学生，而是向学生提供一定的背景资料，由学习者独立操作而习得知识的学习方法是()。
“教是为了不教。”下面摘引的叶圣陶先生的一些论述，其中说明这个名句中“不教”的是()。
中国近代教育史上第一部比较系统，并在全国范围内实施的法定学校系统是()。
布卢姆认识目标分类修订版把知识分为事实性知识、概念性知识、程序性知识和元认知知识四类。下列属于程序性知识的是()。
关于中国四纵四横高速铁路网，下列说法正确的是()。
李大力最近发现，正在读初三的儿子李小力难以保持自我一致性，容易丧失目标，失去信心。依据埃里克森的心理社会性发展理论，李小力个体发展危机没有处理好的阶段是()。
structemployee(10nghum；floatsalary；slructemployee*next；)；intn；structemployee*Create-(){struc
在端到端之间提供可靠数据传输的是计算机网络体系结构中的（）。
假设使用一种加密算法，它的加密方法很简单：将每一个字母加5，即A加密成F。这种算法的密钥就是5，那么它属于()。
随机试题
力的三要素是什么？
患者男性，39岁。1小时前因酒后与人争吵时突然感觉双颞侧剧烈头痛，面色苍白，急送入院。途中曾呕吐胃内容物一次，神志不清、遗尿、全身抽搐约2分钟，入院后约10分钟苏醒，醒后诉头痛及颈痛。既往体健。初步诊断主要考虑哪些疾病
显示肺尖部病变的最佳体位是
犬细小病毒病肠炎型的特异性治疗方法是()
保护房地产权利人的合法权益是产权产籍管理的根本目的和出发点。()
(2006)以下哪项所示的地名是与退思园、兰亭、个园、檀干园四座园林的所在地点相对应的?
法的()特征，集中表明了法与国家的不可分割的必然联系。
()年产生于美国的“大西洋和太平洋茶叶公司”是世界上第一家近代连锁商店，是当时世界生最早的正规连锁商店。
下列各项中，应当确认为负债的是()。
下面说法正确的是()。
最新回复
(
0
)
