首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2019-08-15
47
问题
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
选项
A、O(nlog
2
n)
B、O(log
2
n)
C、O(n)
D、O(n
2
)
答案
A
解析
此题考查的知识点是各类排序的效率。理论上可以证明,对于基于关键字之间比较的分类,无论用什么方法都至少需要进行log
2
(n!)次比较。
由Stirling公式可知,log≈(n!)≈nlog
2
n一1.44n+O(log
2
n),所以基于关键字比较的分类时间的下界是D(nlog≈n)。因此不存在时间复杂性低于此下界的基于关键字比较的分类。应选A。
转载请注明原文地址:https://kaotiyun.com/show/QdCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
苏联实行新经济政策和美国推行罗斯福新政的相似点是()。①面临极为困难的经济形势②国家颁布政策法令强制干预经济③最主要内容是调整和复兴工业④通过发展商品生产来恢复农业
中共八届九中全会提出的恢复和调整国民经济的方针是()。
(1)所有事件的最早发生时间如下:Ve(1)=0Ve(2)==5Ve(3)=6Ve(4)=max{ve(2)+3,ve(3)+6}=12Ve(5)=max{ve(3)+3,ve(4)+3}=15Ve(6)=ve(4)+4=16Ve(7)=ve
在4×100米接力赛中,4个运动员之间存在如下关系:运动员1跑到终点把接力棒交给运动员2;运动员2一开始处于等待状态,在接到运动员1传来的接力棒后才能往前跑,他跑完100米后交棒给运动员3;运动员3也只有接到运动员2传来的接力棒后才能往前跑,他跑完100米
编写一个算法,实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。
某机字长32位,总线数据线宽度是16位,一个总线周期占用4个时钟周期,总线时钟频率为10MHz,则总线带宽是()。
若二叉树的前序序列为DABCEFG,中序序列为BACDFGE,则其层次序列为()。
下列排序算法中,时间复杂度为O(nlogn)且占用额外空间最少的是()。
大部分文件系统以硬盘作为文件存储器。某一个文件系统中,其磁盘物理块的大小为512B,有一个文件,包含了590个逻辑记录,每个记录占255B;其中,为检索方便,采用成组法存储,在每个物理块上只存放2个记录。,文件A在该文件目录中的位置如下图所示。
已知一个带有表头结点的单链表,结点结构为:假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data域的值,并返回1;否则,只返回0。要求:
随机试题
一名25岁哺乳期妇女,婴儿6个月,既往健康。近1个月感觉乏力、低热,因咳嗽、咳痰带血1周前到医院接受诊治。一般检查:体温37.8℃,脉搏86次/分,呼吸18次,分,血压120/80mmHg,双肺呼吸音清最合适的实验室检查是
病例对照研究中,样本大小取决于
女,51岁。绝经5年,阴道脱出肿物,检查宫颈及部分宫体脱出阴道口外。患者的治疗采用的方式是()
医德良心的描述正确的是
某施工单位在南方某地承接了一项移动通信基站安装工程,部分工程利旧,合同约定7月10日开工,10月30日完工。开工前,项目部进行安全技术交底时针对高处作业提出了下列具体措施:(1)作业人员必须佩戴安全帽、安全带,穿工作服、工作鞋。(2)施工时划定安全禁
按照企业价值评估的市价/收入比率模型,以下四种不属于“收入乘数”驱动因素的是( )。
下列各项中,会导致账实不符的有()。
下列关于中国残疾人联合会,说法不正确的是()。
联网计算机在相互通信时必须遵循统一的_______。
WeinheritourDNAfromourparents.DNAisshuffled,recombinedand【B1】______fromonegenerationtoanother.Eachindividualon
最新回复
(
0
)