首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2023-02-06
39
问题
基于比较方法的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
学硕统考专业
相关试题推荐
李磊和几个平时关系不错的同班同学经常一起玩耍，久而久之便形成了一个小群体。他们组成的小群体经常会与班主任和班委会对抗，还不参加集体活动。他们这个群体属于()。
()是班级组织长期形成的言论上、情绪上和行动上的共同倾向，是学生思想、定位、人际关系、舆论力量等方面的精神风貌的综合反映。
教唆他人实施犯罪行为的，均构成共同犯罪。()
强调迁移的条件是两种学习必须遵循共同的内在原理，这是()。
根据联合国官网，联合国大会将“青年”定义为年龄介于15岁至24岁之间(含15岁和24岁)的那些人。根据中共中央、国务院近日印发的《中长期青年发展规划(2016—2025年)》所指的，“青年”年龄范围是14～35周岁。以下各项说法能够从题干中推出的是：
在数宁化多媒体时代，媒介参与的深度和广度日渐拓展，数字技术应用于文化遗产的保护已从原始的简单记录发展到对文化遗产的精准________，运用数字输入、摄像等各种数字化技术对文化遗产进行多形式的________，建立数字化的文化遗产档案和“非遗”博物馆等，都
线上阅读建立起四通八达的内容传播渠道，让我们获取信息的种类和数量更多了，但其并非唯一的阅读形式。事实上，传统的纸质阅读仍是一种不可或缺、具有独特优势、更适合进行深度阅读的重要阅读形式。以下哪项如果为真，最能支持上述观点?
研究人员介绍，来源于化脓链球菌的Cas9核酸酶现已广泛应用于水稻基因组编辑，有效促进了水稻功能基因组学研究和分子育种进程。Cas9在进行基因组编辑的过程中需要识别、结合一段位于编辑位点靶DNA序列末端的保守NGG序列(该保守序列被称为PAM识别序列，N为碱
某部门举行年会抽奖活动。抽奖箱里有80个抽奖券，共20个不同的数字，每个数字均出现4次，且分别对应一份礼品，不同的数字对应的礼品不同。每人当天限抽1次。那么最少多少人当天参加抽奖活动，才能保证至少有3人领取的礼品相同?
随机试题
开车、跳舞、滑冰等属于连续型动作技能。()
适合于需要多部门相互配合或工作具有临时性的组织形态是()
下列哪些疾病在遭受创伤、烧伤等急性损害后更易发生多器官功能不全综合征
要衬托出上唇丰满度，上前牙切缘在唇下应露出
建设工程项目总承包招标又称为建设项目全过程招标，在国外称之为“交钥匙”承包方式。()
在社会主义市场经济条件下,金融的宏观调控功能是以中央银行独立执行货币政策,通过()来实现的。
根据《商标法》规定，以协会名义注册，供协会成员在商事活动中使用，以表明使用者在该协会中的成员资格的标志，属于()商标。
1952年，我国国内生产总值(GDP)仅为300亿美元。1960年，达到614亿美元。之后，每年的GDP总量呈稳步小幅上升态势。1972年突破l000亿美元，之后用了10年的时间达到2021亿美元(1982年)。从此以后，我国GDP总量逐年稳步大幅增加
教师对职业理想、职业人格、职业原则、职业规范坚定不移的信仰是()
下列IPv6地址表示中，错误的是()。
最新回复
(
0
)
