首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2019-01-30
58
问题
基于比较方法的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/uaRi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
两极格局终结的原因、标志及影响是什么?
苏联解体、东欧剧变的根本相同原因是()。
中共中央提出的“坚持抗战，反对投降；坚持团结，反对分裂；坚持进步，反对倒退”的口号，主要是针对()。
鉴于汉匈关系的状况，汉初向汉高祖提出和亲政策的是()。
美国首次提出争夺世界霸权的纲领性文件是()。
宋代至清代我国书籍印刷的主要方式是()
1861年俄国废除农奴制改革的主要作用是()。①造成资本集中②扩大了国内市场③增加了自由劳动力④强化了中央集权
在下面哪本著作中以异化劳动理论的形式阐述了一种新的科学世界观的雏形?()
以下不属于国民党控制金融的“四行”是()。
系统地阐明道家思想的著作《淮南鸿烈》，也叫《淮南子》，是汉武帝时()集宾客写成的。《淮南子》问世时，黄老思想在政治上已不占支配地位了。
随机试题
中性层的位置与材料的()无关。
A．肺结核病的各种X线表现斑点、条索、结节状，边缘清楚，密度较高B．云雾状，密度较淡、或密度不均边缘模糊阴影C．密度较高，浓淡不一，呈小叶或大叶分布片状影D．有环形边界的透光区E．大片均匀致密影，上缘呈弧形向上硬结病灶
β受体阻断药同时具有。受体阻断作用的是
甲、乙、丙、丁计划设立一家从事技术开发的天际有限责任公司，按照公司设立协议，甲以其持有的君则房地产开发有限公司20％的股权作为其出资。下列哪些情形会导致甲无法全面履行其出资义务?
根据《生活垃圾填埋场污染控制标准》，关于生活垃圾转运站渗滤液处理方式，说法正确的是()。
期货公司执行客户交易指令，数量发生错误的，下列说法正确的有()。
某企业拟购买一套设备，厂商提供两种付款方式：第一种，一次性立即付款，价格为100000元。第二种，自第3年年初开始，每年付款30000元，连续支付5年。要求：假定市场利率为10%，企业应选择哪种付款方式?
一般来说，技术基础雄厚的大型企业，大都采用的创新模式是()。
BeautyisbigbusinessinChina.Thecountry’scosmeticsmarketisworth$26billionayear,makingitthethird-biggestinthe
Whydon’tbirdsgetlostontheirlongflightsfromoneplacetoanother?Scientistshavebeenpuzzledoverthisquestionforma
最新回复
(
0
)
