首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2017-11-14
55
问题
基于比较方法的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/C3Ri777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列对第三次科技革命推动了国际经济格局调整的叙述，不正确的是()。
1925年爆发的当时世界上罢工时间最长的一次斗争是()。
1905年至1907年间，围绕中国究竟是采用革命手段还是改良方式这个问题，革命派与改良派进行论战的舆论阵地是()。
关于美国内战，不正确的说法是()。
美国工业革命的有利条件包括()。①美国自然资源丰富②独立战争后，美国创立了资产阶级共和制度③地理位置优越，远离动乱的欧洲④拥有潜在的广阔的国内市场
戈尔巴乔夫上台后，在和平共处五项原则基础上，推动苏中关系正常化，这一做法主要表明了()。
明成祖时期大力推崇理学，以国家力量编写了几部理学的大部头著作，下面不属于其中的是()。
下列不属于延安整风运动的文件是()。
在“冷战”形成的过程中，影响苏联领导人对美政策变化的关键性事件是()。
随机试题
简要回答短销售渠道优于长销售渠道的原因。
牙齿的萌出是指A．牙齿出龈B．牙胚突破牙囊C．牙冠出龈及到达咬合的过程D．牙齿咬合E．牙胚形成到牙冠出龈
A、西咪替丁B、尼扎替丁C、法莫替丁D、雷尼替丁E、罗沙替丁乙酸酯口服吸收迅速但不完全，口服生物利用度约50％，且不受食物影响的是()。
《处方管理办法(试行)》规定，医师处方和药学专业技术人员调剂处方应当遵循的原则是()
“会计电算化”一词始于()。
下列关于物权基本原则的表述中，不符合法律规定的是()。
根据我国宪法的规定，下列属于国务院依法行使职权的是()。
社会形态是()
Whatkindsofpeopleoftengivedrugstotheirchildren?Whereintheworlddopeopledragbeforegoingtowork?Theanswersare
Whenitcomestotheslowingeconomy,EllenSperoisn’tbitinghernailsjustyet.Butthe47-year-oldmanicuristisn’tcutting,
最新回复
(
0
)
