首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2017-01-04
80
问题
基于比较方法的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
学硕统考专业
相关试题推荐
1961年10月,在苏共二十二大上,赫鲁晓夫宣布苏联基本建成共产主义的时间是()。
胡适与李大钊进行“问题与主义之争”的主战场是()。
英国封建制度形成的过程。
拜占庭帝国的第二个黄金时代是在()。
美国的垄断组织主要采取的形式是()。
下面关于新经济政策的说法不正确的一项是()。
1628年出版了《心血运动论》一书,论证了血液在全身的循环运动,使生理学发展为科学的是()。
凡尔赛体系是由一系列条约组成的,其中战胜国与匈牙利签订的条约为()。
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
某机的主要部件如下图所示。(1)请补充各部件间的主要连接线,并注明数据流动方向。(2)拟出指令SUB(R1),一(R2)的执行流程(含取指过程与确定后继指令地址)。该指令的含义是进行减法操作,源操作数地址和目的操作数地址分别在
随机试题
人民法院判决被告重新作出行政行为的,被告不得以同一的事实和理由作出与原行政行为()的行政行为。
________comesbackfirstissupposedtowintheprize.
Iamoftenaskedtodescribetheexperienceofraisingachildwithadisability.Itislikethis.【C1】______youaregoingtohav
患者大汗不止,汗出如油,神情恍惚,心慌气促,声短息微,四肢逆冷,二便失禁,舌卷而颤,脉微欲绝,首选方剂是
患儿,1岁半,诊断为“营养性缺铁性贫血”,需口服铁剂治疗。护士对家长进行应用铁剂的指导,其中不正确的是
心脉痹阻可以引起肠痈可以引起
谵语的病因病机多由于
白芷的主产地为
下列国家中实行“授权资本制”的有()。
下列选项中关于物权的公示公信原则,说法错误的是()
最新回复
(
0
)