首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2017-11-14
38
问题
基于比较方法的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
学硕统考专业
相关试题推荐
北庭都护府
中国第一个资产阶级革命团体兴中会建立的时间是()。
“我不想变成上帝,或居住在永恒之中,或者把天地抱在怀里,属于人的那种光荣对我就够了。我自己是凡人,我只要求凡人的幸福。”这句话体现的思想是()
“国际工人协会”宣布成立后,10月协会选出了第一任主席,他是()。
乾隆时期,明确规定了驻藏大臣的地位与达赖班禅同等,并实行“金瓶掣签”制度的文件是()。
19世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
洋务派创办军事工业的方式是()。
一个TCP连接总是以1KB的最大段发送TCP段,发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时,如果接下来的4个RTT(往返时间)时间内的TCP段的传输都是成功的,那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时,拥塞窗口大小是
假设系统的所有资源是同类型的,系统中的进程每次申请资源数最多1个,那么,下面列出的4种情况中,()可能发生死锁。情况序号系统中进程数资源总量
假设有k个关键字互为同义词,若用线性探查法把这k个关键字存入,至少要进行的探查次数是()。
随机试题
A.钙B.钾C.镁D.锌E.铜对维持细胞膜通透性及细胞间黏着性有一定作用的是
以下各种疾病最容易发生夜间阵发性呼吸困难的是
甲类传染病的法定传染病报告时间,在城镇应于发现后
含有某一发色团的药物,最大吸收波长为230nm,其跃迁类型为( )。
《建设工程工程量清单计价规范》(GB50500-2013)规定,招标时用于合同约定调整因素出现时的工程材料价款调整的费用应计入()中。
甲投资方案投资当年的预期通货膨胀率为5%,名义折现率为11.3%。则该方案的实际折现率为()。
下列选项中,以故意杀人罪论处的是()
在Client/Server系统中,服务器主要做数据库的管理,按数据请求进行数据处理并回送结果。根据服务器的上述特点,Client/Server系统对服务器的要求是
•YouwillheararadiointerviewbetweenawomanjournalistandMichaelDell,ChairmanofDellInc.andhisnewCEO,KevinRolli
Almostacenturyafterhisdeath,thewell-knownFrenchauthorJulesVernehasonceagainmanagedtofiretheimaginationofpeo
最新回复
(
0
)