首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2017-01-04
44
问题
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
选项
A、O(nlog
2
n)
B、O(log
2
n)
C、O(n)
D、D(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/mQRi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述士族的源流和在西晋的发展过程。
简述第二国际建立的社会历史条件。
两次世界大战之间的国际关系是怎样维持的?
开皇三年，隋文帝下令州县官吏根据户籍簿上登记的年龄，来核对本人体貌，以防诈老诈小逃避租役，是为()。
世界天文史上最早实地测量子午线的记录是由谁进行的?()
下列关于清朝军机处的叙述，不正确的是()。
战时共产主义政策中对后来的工农联盟最能构成威胁的是()。
阅读下列史料，并回答问题：在琶勒尼斯(注：地名)一役获胜后，他(庇西特拉图)便占领政府，并解除人民武装；现在他已能稳定地握住僭主政权，并且取得那克索斯。以吕格达密斯为统治者。他解除人民武装的方法是这样的：他在塞修斯庙举行了一个武装的阅兵式，同时举行一次民
设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][O]的存储地址为860，则a[3][5]的存储地址为()。
现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2．…，em)；i＝l；while(所剩边数>＝顶点数){从图中删去ei；若图不再连通，则恢复ei；i＝i＋l；
随机试题
机关物资管理的主要内容有：①______。②______。③______。④________。
在Word中，下面________说法是正确的。
下列哪一项舒张期正向血流速度最大
2个月婴儿来院体检，护士指导家长每日定时播放音乐，近距离和孩子说话，在房间内张贴鲜艳图片，拿颜色鲜明、能发声的玩具逗引孩子。其目的是促进该婴儿()。
①春秋战国时期，游牧民族将这种镶嵌玻璃珠由西亚带入中国②公元前10世纪，在玻璃珠母体上镶同心圆，制造出“眼睛”效果的镶嵌玻璃③玻璃又称琉璃，公元前2500年人造玻璃首次出现于西亚及埃及，最早的用途是制造珠饰④公元前15世纪玻璃珠上开始有彩斑条纹或点状
测绘计量检定人员资格考试于每年()举行一次。
下列属于基础工程施工安全控制的主要内容的是()。
某供水运营管理单位2013年占用土地100000平方米，房产原值10000万元。全年供水量为16亿万立方米，其中向农村居民年供水量为4亿万立方米，该供水运营单位所在地计算房产余值的减除比例为20％，城镇土地使用税年税额为3元／平方米。2013年该企业应缴纳
Theconversationbetweenthestateleadersledtoanewfocus_____publichealth．
研究者通过感官或者一定仪器设备，有目的、有计划地观察儿童的心理和行为表现，并由此分析儿童心理发展的特征和规律的一种方法是()
最新回复
(
0
)
