首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
公务员
利用比较的方法进行排序，在最坏情况下，能达到的最好时间复杂度是多少?请给出详细证明。
利用比较的方法进行排序，在最坏情况下，能达到的最好时间复杂度是多少?请给出详细证明。
admin
2013-12-19
76
问题
利用比较的方法进行排序，在最坏情况下，能达到的最好时间复杂度是多少?请给出详细证明。
选项
答案
假定特排序的记录有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
计算机专业知识
事业单位考试
相关试题推荐
信息加工理论对实际教学的启示是()。
下列关于公文写作的说法正确的是()。
布鲁纳认为，无论我们选择何种学科，都务必使学生理解该学科的结构，以此建立的课程理论是()。
学生在看书时，用红色划出重点，以便重新阅读，这是利用知觉的整体性。()
计算机辅助教学中的教学模式是()的有机结合，是为完成现代教学与学习任务采用的相对稳定的，用以设计、组织、实施、评估、优化教学与学校的策略方法和结构的简化形式。
在计算机网络中，TCP／IP是一组支持同类型的计算机(网络)Ni联的通信协议。()
structemployee{longnum；floatsalary；structemployee*next；}；intn；struetemployee*del(struet
一台主机或路由器同因特网有多个接口，为保证唯一性，其只能拥有一个IP地址。()
Internet使用TCP／IP协议实现了全球范围的计算机网络的互联，连接在Intemet上的每一台主机都有一个IP地址，下面哪一个不能作为IP地址?（）
某一用户想为一个Word文档设置密码，以下操作不正确的是()
随机试题
行政法律责任必须由有关（）依照行政法律规范,包括实行规范和程序规范所规定的条件和程序予以追究。
原发性肝癌最常见的组织学类型为
A、吸收散射线B、吸收漏射线C、减少照射野D、抑制散射线E、吸收原发低能射线滤线栅的作用是
单位保证金存款按照保证金担保对象的不同，可以分为()。
A注册会计师拟实施穿行测试，不属于注册会计师执行穿行测试目的是()。
在上次考试中，老师出了一道非常古怪的难题，有86%的考生不及格。这次考试之前，王见明预测说：“根据上次考试情况，这次考试老师不一定会出那种难题了。”胡思明说：“这就是说这次考试老师肯定不出，那种难题了。太好了!”王见明说：“我不是这个意思。”下面哪
对于假想防卫，应当()。
下列数据结构中，能用二分法进行查找的是
ATheSpeechofthePresiderThepresidingovermeetingsisoneofthecommunicativeactivitiesatinternationalacademicconfer
A、TheychallengedSerenaWilliams’sethnicity.B、TheyfollowedtherolemodelofSerenaWilliams.C、Theyraisedanumberofcomp
最新回复
(
0
)
