首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2023-02-06
69
问题
基于比较方法的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．阆中的乡村学校大都依山而建，地形狭长而起伏。在经过若干年的撤点并校之后，形成了以九年一贯制的中心学校为主体的格局。校园都有相似之处，但又会让来访者耳目一新，其中有许多教育局要求的“标配"，比如用学生们的彩色大头照拼成的“笑脸墙"，师生共同
师徒二人用15天合作生产1000个零件，前5天师傅的效率是徒弟的2倍，中间5天师傅休息，徒弟每天比原来多生产5个零件，最后5天两人又一起工作，师傅的效率不变，徒弟的效率比中间5天提高了50％，徒弟这15天生产的零件个数是：
深度学习是指在模仿人脑机制的神经网络中，对人工神经元的层进行了“多层处理”。深度学习不仅可以让AI(人工智能)读取大量图片，还可以让AI自主提取图片特征。得益于深度学习技术的面世，只要有大量数据，AI就能以极高的准确率进行学习，从而大幅度拓展了AI的应用范
从所给四个选项中，选出能与给定的①、②、③、④零件共同构成如下图所示的9×2方块组合的一项：
文化是怎么来的?似乎是一些学者、作家、艺术家、宗教家折腾出来的，其实这一看法过于________。往深层次看，所有文化形态后面都有某种生态的条件和诱因，广义的生态元素——包括地理、气候、物种等——总是参与对文化形成的制约和________。填入画横线部分最
过滤气泡是指以大数据与算法推荐为底层架构，根据用户的使用时间、地区以及浏览习惯生成用户画像，并通过算法技术为其呈现独一无二的界面体验。网络上这种针对个人化搜索而提供筛选后结果的推荐算法，被称为过滤气泡。根据上述定义，下列不属于过滤气泡的是：
下列关于《国务院关于加快建立健全绿色低碳循环发展经济体系的指导意见》提出的主要目标的说法，错误的是()。
随机试题
女性，25岁，发热、咳嗽、流涕2周后热退，但又出现胸闷心悸，心率120次/分，心律不齐，偶闻早搏，心电图：低电压，T波低平，应首先考虑
个人理财最早在()兴起并首先成熟。
某公司在6年建设期内每年年末从银行借款120万元，借款年利率为10％，则该项目竣工时应付本息的总额为()万元。
知觉恒常性是指当知觉条件在一定范围内改变时，人们对事物的知觉印象却可以保持相对稳定不变的特性，知觉恒常性包括形状、大小、明度、颜色和运动恒常性等多种。根据上述定义，下列不能用知觉恒常性解释的是：
程序流程图中带有箭头的线段表示的是( )。
A、B、C、D、B
Dr.BethunecamefromCanadaandWasveryWarmtowardstheWounded.Helovedeverypeople’sfighter.HeWasalwaysinthesickroomo
A、 B、 C、 A题目为询问是否应该由说话者自己来预约欧洲之旅的助动词(Should)疑问句。ShouldI…可用来表达“我需要／应该……吗?”。
St.Patrick’sDayiscelebratedonMarch17,hisreligiousfeastdayandtheanniversaryofhisdeathinthefifthcentury.Lege
Allhisaffairsareupintheair.Theunderlinedpartmeans______.
最新回复
(
0
)
