首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2023-02-06
53
问题
基于比较方法的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．近年来，学校的学业负担让很多学生不堪重负，长时间的课业学习不仅让学生们得不到充分的休息，也让本应属于他们的欢快的课余生活被枯燥的课业学习所取代。减负政策的实行仿佛让学生们看到了希望的曙光，但在减负政策逐步推行的过程中，部分政策其实并没有真正落
下图右框内纸盒的外表面中，不能折叠成左框内所示的纸盒的是：
微生物是地球最早出现的生命形式，这种简单而古老的生命决定了地球演化的方向和进程，推动了土壤的发生和发育，孕育了人类的文明。事实上，土壤中蕴藏的微生物的多样性，被称为地球关键元素循环过程的引擎，是联系大气圈、水圈、岩石圈及生物圈物质与能量交换的重要纽带，维系
在公众对不同信息源的信任层级排序中，来自政府的消息历来以权威性和________居于前列。同样是传谣，谣言经政府官微传播后破坏力更强，这________。填入画横线部分最恰当的一项是：
研究人员介绍，来源于化脓链球菌的Cas9核酸酶现已广泛应用于水稻基因组编辑，有效促进了水稻功能基因组学研究和分子育种进程。Cas9在进行基因组编辑的过程中需要识别、结合一段位于编辑位点靶DNA序列末端的保守NGG序列(该保守序列被称为PAM识别序列，N为碱
随机试题
被鲁迅称为“西汉宏文”的作品是（）。
下列哪种说法是错误的()(1994年第34题)
化学性污染物进入人体的主要途径是
微球的主要类型包括
在弹性媒质中传播的一平面简谐波，某一时刻在传播方向上媒质中某质元在负的最大位移处，其能量是()。
MissYangwillteachusChinesetoday______MrZhang.
民警在辖区内的城市森林公园巡逻时，发现有母女二人在路边惊恐啼哭并不时用纸巾擦拭腿上的血迹。经了解得知，母女二人刚才被一条烈性犬咬伤，无人看管的烈性犬就在前方不远处趴卧并露出凶相，随时有可能攻击行人，行人见状纷纷躲避。民警以下措施不正确的是：
新中国成立之初，中国共产党面临的考验主要有()。
______arethosethatcannotbeusedindependentlybuthavetobecombinedwithothermorphemes,eitherfreeorbound,toforma
Ifthesupplyofvitaminsandmineralsinthedietis______,thiswillresultinchangesinbodychemistry.
最新回复
(
0
)
