首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2017-01-04
59
问题
基于比较方法的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
学硕统考专业
相关试题推荐
简述雅典民主政治的形成过程。
简述苏联和南斯拉夫之间的冲突。
斯蒂文逊负责勘测和修建的世界上的第一条公共交通铁路通车于()。
在1875年宪法中关于法国立法权的叙述,不正确的是()。
凡尔赛体系是由一系列条约组成的,其中战胜国与匈牙利签订的条约为()。
下列改革内容不是在《天朝天亩制度》中提出的一项是()。
1920年,苏俄农民中流传着这样的说法:“土地属于我们,面包却属于你们;水属于我们,鱼却属于你们;森林属于我们,木材却属于你们”,它反映的是战时共产主义政策()。
中国第一条自行设计修建的铁路是在()。
一个TCP连接总是以1KB的最大段发送TCP段,发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时,如果接下来的4个RTT(往返时间)时间内的TCP段的传输都是成功的,那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时,拥塞窗口大小是
某模型机的通路结构如下图所示,用寄存器传送语句(如PC→MAR),拟出下列指令从读取到执行的完整流程。(1)数据传送指令MOVX(R0),Y(R1),源和目的操作数地址均采用变址寻址,第1个参数X为源操作数的形式地址,第2个参数为目的操作数的形
随机试题
下列游戏不属于创造性游戏是()。
资产负债表
对支气管哮喘患者,下列护理措施正确的是
患者,女,33岁。因发热、胸痛、咳痰2日入院。体检:体温40℃,右下肺闻及湿啰音。血白细胞计数12.0×109/L。入院诊断为:发热待查:肺炎?。该患者的护理问题是
()是按照市场供求状况而自由变动的利率,它主要反映了市场内在力量对利率形成的作用。
背景某医院由多幢大楼(门诊楼、急诊楼、住院楼和综合楼等)组成,安装公司承包了该医院的机电工程,机电工程内容有建筑给水排水、建筑电气、通风空调、智能化等工程。工程合同约定为固定总价5000万元,每幢大楼完工后立即进入竣工验收。工程的设备、材料均由业
某用人单位招聘一名员工,由于工作疏忽一直未与其签订劳动合同;一年后,用人单位决定辞退该员工,在用人单位应承担的法律后果中错误的是()。
下列有关财务管理目标表述中,正确的是()。
仙都现存摩崖石刻和题记120余处,最早的摩崖石刻为唐代乾元元年小篆书法家李阳冰题写的()三字,以及建中元年的一篇游记。
A、 B、 C、 D、 A第一组图形分别由一画,两画,三画组成,第二组也遵循同样规律,所以选A。
最新回复
(
0
)