首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2017-11-14
46
问题
基于比较方法的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年爆发的当时世界上罢工时间最长的一次斗争是()。
()时，为补充兵力，开拓财源，“料民于太原”(今山西西南部)。料民就是清查民数，以便于征兵，结果引起奴隶和平民的反抗。这表明西周王朝已失去了对社会的控制力量。
19世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。
阅读材料，回答以下问题：重庆中央党部，暨中央执监委员诸同志均鉴：今年4月，临时全国代表大会宣言，说明此次抗战之原因，曰：“自塘沽协定以来，吾人所以忍辱负重与倭国周旋，无非欲停止军事行动，采用和平方法，先谋北方各省之保全，再进而谋东北四省问题之合理解决，
基辅罗斯国家对居民征税的方式是()。
第一次国共合作采取了共产党员以个人身份加入国民党的“党内合作”方式。最早提出这种方式的是()。
系统地阐明道家思想的著作《淮南鸿烈》，也叫《淮南子》，是汉武帝时()集宾客写成的。《淮南子》问世时，黄老思想在政治上已不占支配地位了。
设磁盘的扇区大小为4KB，磁盘转速为15000r／min，磁盘平均寻道时间为4ms，最大数据传输速率为40MB／s，磁盘控制器开销时问为1ms，计算读写一个扇区所需平均时间(不考虑I／O请求队列中的等待时间)。
在下列排序方法中不需要对排序码进行比较就能进行排序的是()。
随机试题
2016年上半年，某市经济保持了稳定的发展势头，上半年实现GDP1894．3亿元，同比增长7．4％，比一季度加快0．3个百分点。其中，第一产业增加值68．2亿元，同比增长3．3％；第二产业增加值1098．9亿元，同比增长8．5％；第三产业增加值727．
kindlyadviseusofthesteamersthatcall_______yourporteverymonth.
基金托管人开展基金托管业务的准备阶段是()
根据《中华人民共和国担保法》的规定，定金的数额由当事人约定，其最高数额为主合同标的额的( )。
甲公司(增值税一般纳税人)向乙公司一次性购入三台型号不同的机器设备A、B、C，取得增值税专用发票注明的金额为1800万元，增值税税额为288万元，支付运费取得增值税专用发票注明运费12万元，增值税税额1．2万元。已知设备A、B、C的公允价值分别为1000万
理论上，下列债券中票面利率最低的应该是()。
根据我国有关法律的规定，下列各项中属于《对外贸易法》适用范围的有()。
向量a=(1，2)，b=(x，1)，c=a+b，d=a－b，若C∥d，则实数x的值等于()．
A、42B、43C、44D、45A(2+4+5)×2=22，(3+7+6)×2=32，(5+6+8)×2=38，所以?=(7+5+9)×2=42，正确答案是A选项。
关于著作权的作者，下列说法不正确的是()
最新回复
(
0
)
