首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2017-11-14
32
问题
基于比较方法的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/C3Ri777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
【辉格派】南京大学2005年世界史真题
1956年,苏共二十大后,匈牙利大党员和群众强烈要求克服个人崇拜,扩大民主,实行经济改革,一些由知识分子、大学生和干部组成的社团组织纷纷成立,其中最有影响者是()。
1905年至1907年间,围绕中国究竟是采用革命手段还是改良方式这个问题,革命派与改良派进行论战的舆论阵地是()。
戈尔巴乔夫上台后,在和平共处五项原则基础上,推动苏中关系正常化,这一做法主要表明了()。
古希腊是西方文明的发源地,古希腊雅典的民主政治则开启了两方民主制度的先河。下列关于雅典民主政治的说法,符合史实的有()。①民主政治时期的雅典没有国王②公民大会是雅典国家的最高决策机构③伯里克利时期,雅典民主政治达到了顶峰④包括妇女在内的
西汉初年,反驳刘邦“马上治天下”的说法,并向汉帝国治国献策的是()。
第一次国共合作采取了共产党员以个人身份加入国民党的党内合作方式,最早提出这种方式的是()。
利玛窦与徐光启合作翻译的(),介绍了曾经流行于欧洲的欧几里得平面几何的系统理论,大大地丰富了中国古代几何学的内容。
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
写出单总线结构计算机中指令M()VER1,R2(含义是将寄存器R1中内容写入寄存器R2中)的操作步骤。
随机试题
按运用权力和权威的程度分类,工会属于()
利用Windows提供的剪贴板,可选择下列_______操作,即可完成文本、图形和文件等对象的复制
会使气道黏膜清除减慢的因素包括以下各项除了
属适应性免疫应答的是
若患者脓血便,提示其可能的病证为()。
关于施工企业营业收入的说法,正确的是()。
企业因在职工劳动合同到期之前解除与职工的劳动关系给予职工补偿而发生的职工薪酬,应借记()科目。
下列哪一个数介于1/2与2/3之间()。
许多高等教育机构在经济增长放缓时期面临招收学生人数下降的问题。但是在两年制社区的大学里,这段时期当许多入收入减少并且为获得工作的竞争更加激烈时,招收学生的人数大量增加。以下各项如果正确,都有助于解释以-卜描述的两年制大学招生人数增加的情况,除了:(
WhenyouwalkintoaNationalForest,youreallybelieveyou’rethefirstpersonwho’severbeenhere.Funnythingis,you’reno
最新回复
(
0
)