首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2023-02-06
55
问题
基于比较方法的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/XIwD777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
()是个体品德的核心部分,指一个人面对矛盾冲突的情景能自觉意识到是非善恶,进而能就行动做出缜密周到的抉择。
《中华人民共和国义务教育法》规定:“家长应当依法保障适龄儿童、少年接受义务教育权利的实现”。这种法律规范属于()。
经典条件反射的建立过程与操作条件反射的建立过程无根本差异。()
给定资料: 1.阆中的乡村学校大都依山而建,地形狭长而起伏。在经过若干年的撤点并校之后,形成了以九年一贯制的中心学校为主体的格局。校园都有相似之处,但又会让来访者耳目一新,其中有许多教育局要求的“标配",比如用学生们的彩色大头照拼成的“笑脸墙",师生共同
疫情导致全国产业格局重塑,中国国内也面临严峻挑战,中国将________内陆的新基建投资和消费转型构建稳定的国内循环,巩固脱贫攻坚成果与乡村振兴的有机________。进一步为深化中国自然资本增值和重塑区域经济提供新的方向。依次填入画横线处最恰当的一项是:
深度学习是指在模仿人脑机制的神经网络中,对人工神经元的层进行了“多层处理”。深度学习不仅可以让AI(人工智能)读取大量图片,还可以让AI自主提取图片特征。得益于深度学习技术的面世,只要有大量数据,AI就能以极高的准确率进行学习,从而大幅度拓展了AI的应用范
如下图1所示,在一个金字塔造型(底面为正方形,侧面为四个全等的等腰三角形)的铸造件内部挖空一个圆柱。现沿铸造件顶点A且垂直底面的方向切开,切开后的截面如下图2所示,已知DE、GF为圆柱的高,BC=4分米,DE=2分米,AO=4分米,那么挖后铸造件的体积是:
研究人员介绍,来源于化脓链球菌的Cas9核酸酶现已广泛应用于水稻基因组编辑,有效促进了水稻功能基因组学研究和分子育种进程。Cas9在进行基因组编辑的过程中需要识别、结合一段位于编辑位点靶DNA序列末端的保守NGG序列(该保守序列被称为PAM识别序列,N为碱
小张、小王、小李三人相约骑自行车出去旅行,出发时约好某地集合。小张、小王两个人早上5时从约好的地点出发,小张每小时骑行18千米,小王每小时骑行14.4千米。小李因有事耽搁,早上7时才从约好的地点出发,结果下午5时小张、小李同时到达目的地。假设三人的骑行速度
下列关于《国务院关于加快建立健全绿色低碳循环发展经济体系的指导意见》提出的主要目标的说法,错误的是()。
随机试题
认识保险要从认识危险入手。()
女性,38岁,因甲状腺功能亢进入院,准备择期接受甲状腺大部分切除术治疗。体温36.5℃,脉搏110/min,呼吸18/min,血压120/75mmHg。术前进行药物准备的主要目的是()。
某岩石天然状态下抗压强度为80MPa,饱水状态下抗压强度为70MPa,干燥状态下抗压强度为100MPa,该岩石的软化系数为下列何值?()
某机电安装工程公司承接一汽车厂重型压力机车间机电设备安装工程,工程内容包括设备监造,压机的就位安装、压力管道安装、自动控制工程、电气工程和单机试运行等。其中压机最高22.5m,单件最重为105t,合同工期为4个月。合同约定,工期每推迟一天罚10000元,提
企业在设置会计科目时,允许企业在不违背会计准则的前提下,在不影响会计核算要求和会计报表指标汇总的条件下,根据实际情况自行设置一些科目。()
2013年10月份,社会消费品零售总额21491亿元,同比名义增长13.3%。其中,限额以上企业(单位)消费品零售额10579亿元,增长12.4%。1~10月份,社会消费品零售总额190308亿元,同比增长13.0%(见下图)。按经营单位所在地分,10
结合教学实际,谈谈如何在教学中培养学生的创造性。
为了增强版面的可读性与实用性,经常将文稿进行分栏设置。如果要取消分栏时,在“分栏”对话框中,设置分栏的数目为()。
在用户单位制定项目建设任务书,并且确定网络信息系统建设任务之后,项目承担单位的首要任务就是网络用户调查和()。
Threebasicpathophysiologicmechanismsleadtovirtuallyalltheclinicaldiseasestatesinvolvingendocrineglands:(46)thee
最新回复
(
0
)