首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2019-05-20
68
问题
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
选项
A、O(nlog
2
n)
B、O(log
2
n)
C、O(n)
D、O(n
2
)
答案
A
解析
此题考查的知识点是各类排序的效率。理论上可以证明，对于基于关键字之间比较的分类，无论用什么方法都至少需要进行log
2
(n!)次比较。
由Stirling公式可知，log
2
(n!)≈nlog
2
n一1．44n+O(log
2
n)。所以基于关键字比较的分类时间的下界是O(nlog
2
n)。因此不存在时间复杂性低于此下界的基于关键字比较的分类。应选A。
转载请注明原文地址:https://kaotiyun.com/show/t2Ci777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
基辅罗斯国家对居民征税的方式是()。
西周的官僚制度已经相当完备，官僚机构庞杂，职官名目繁多。周王室的官僚机构分为两大系统，分别是()。
关于罗马奴隶制，下列说法不正确的是()。
从“鲁尔危机”的发生到《道威斯计划》的实施，西方国际关系变化对当时有关国家的影响是()。①美国势力进一步向欧洲渗透②英国达到了限制法国、保持均势的目的③德国获得重建经济的有利时机④法国扩充实力争霸欧洲的计划遭
(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，
某机字长32位，它的存储容量为256MB，按字节编址，则它的寻址范围大小为()。
一个使用选择性重传协议的数据链路层协议，如果采用了5位的帧序列号，那么可以选用的最大窗口是()。
设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][O]的存储地址为860，则a[3][5]的存储地址为()。
在微指令的编码方式中，若微命令数相同，下列叙述中正确的是()。I．直接控制方式与编码控制方式的微指令长度相等Ⅱ．最短编码控制和直接控制方式不影响微指令字长Ⅲ．编码控制方式的微指令比直接控制方式的微指令短Ⅳ．
随机试题
电子商务环境
A．动作电位B．阈电位C．局部电位D．静息电位兴奋性突触后电位是
背景某公司中标承建中压燃气管线工程，管径DN300mm，长26km，合同价3600万元。管道沟槽开挖过程中，遇地质勘察未探明的废弃砖沟，经现场监理工程师口头同意，施工项目部组织人员、机具及时清除了砖沟，进行换填级配石处理，使工程增加了合同外的工程
当单位利益与社会公众利益发生冲突时，会计人员应该首先维护社会公共利益。()
为了避免漏接，导游员无论在什么交通港接站，都必须至少提前()分钟到达。
根据下列材料回答问题。2010年，我国共投入研究与试验发展(R＆D，以下简称R＆D)经费7062．6亿元，比上年增长21．7％；R＆D经费投入强度(与国内生产总值之比)为1．76％，比上年的1．70％有所提高。分活动类型看，全国用于基础研
党对军队的绝对领导通过一整套制度来实现和保证。这些制度有()
在SQLServer中，若要授予用户U1在DB1数据库中具有创建视图的权限，下列授权语句正确的是()。
GoingonaDietAtypicalpersonneedsabout1,800caloriesperdaytostayalive.Thesecalorieskeepyourheart【C1】______
WritingaJobApplicationYourapplicationisthefirstcontactyouwillhavewithanemployer.Theemployerwilluseitto
最新回复
(
0
)
