首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2017-01-04
26
问题
基于比较方法的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
学硕统考专业
相关试题推荐
简述鸦片战争的三个阶段。
近代自然科学产生的条件及其发展情况。
简述工农武装割据存在与发展的原因和条件。
简述苏联和南斯拉夫之间的冲突。
1901年6月,发表《立宪法议》,首先提出君主立宪要求的是()。
“我不想变成上帝,或居住在永恒之中,或者把天地抱在怀里,属于人的那种光荣对我就够了。我自己是凡人,我只要求凡人的幸福。”这句话体现的思想是()
巴黎和会上,英美主张把原德国在山东的权利转让给日本,华盛顿会议又表示支持中国让日本归还山东的要求,英美态度发生变化的根本原因是()。
下列城市:①南京②厦门③天津④杭州,按其在近代历史上开放为商埠的时间先后顺序排列应该是()
法国里昂工人起义提出:“我们只有一个口号‘人人自由平等!’”英国宪章运动请愿书提出:“我们竭尽自由人的义务,就应享受自由人的权利。我们要求普遍选举。”这些要求表明()。①带有空想社会主义色彩②当时工人的要求还没有超出资产阶级民主主义的范畴
一台模型机共有7条指令,主频25MHz,各指令的使用频率与CPI如下表所示,该机有8位和16位两种指令字长,采用2—4扩展操作码。8位字长指令为寄存器一寄存器(R—R)二地址类型,16位字长指令为寄存器~存储器(R—M)二地址变址类型(地址码范围在一12
随机试题
一国之内适用于不同宗教、种族、不同阶级的人的法律之间的冲突是()
下列不符合《拣麦穗》一文写作特点的说法是()
琥珀胆碱在体内消除迅速系由
关于证券投资基金“集合理财、专业管理”这一特点的具体体现,以下表述错误的是()。[2015年12月真题]
中国证监会及其派出监管机构依法对证券公司的经纪业务进行监管,主要监管措施包括()。Ⅰ.证券公司向监管机构的报告制度Ⅱ.信息披露Ⅲ.检查制度
某人分期付款购买一价值500000元的房产,为还款需每年末在银行存人85228.22元,每年存款,年利率为8%,请问()年才能还清。
人的本质是永恒不变的。()
恩格尔系数是指食物支出金额占总支出金额的比例。恩格尔定律是指随着家庭生活水平的提高,食品的消费支出占家庭总消费支出的比率减少的规律。依据上述定义,下列说法正确的是( )。
以下对于主流嵌入式操作系统的叙述,错误的是()。
Shenoticedtheoldlady’shand______constantlyduringthetalk.
最新回复
(
0
)