首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2017-11-14
78
问题
基于比较方法的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/C3Ri777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
“我不想变成上帝,或居住在永恒之中,或者把天地抱在怀里,属于人的那种光荣对我就够了。我自己是凡人,我只要求凡人的幸福。”这句话体现的思想是()
1920年,苏俄农民中流传着这样的说法:“土地属于我们,面包却属于你们;水属于我们,鱼却属于你们;森林属于我们,木材却属于你们”,它反映的是战时共产主义政策()。
改革开放以后,我国农村产业结构巨大的转变表现在()。
根据越南战争的起源和发展,分析“冷战”时期美国对第三世界政策的目标和动机。
西汉初年,反驳刘邦“马上治天下”的说法,并向汉帝国治国献策的是()。
以海地和巴西为例,论述19世纪拉丁美洲民族独立运动类型多样化的历史依据。
周王室的两大官僚系统是()。
唐朝时期,每丁服徭役二十天,是为正役,国家若不需要其服役,则每丁可按照每天交纳绢三尺或布三尺七寸五分的标准,交足二十天的数额以代役,称为()。
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
随机试题
A、breakB、steakC、greatlyD、breakfastD
试述新民主主义革命的前途及党在这一问题上的历史教训。
()是工程项目管理的前提,也是工程造价管理的前提。
根据《建设工程质量管理条例》,建设工程承包单位在向建设单位提交工程竣工验收报告时,应当向建设单位出具()。
下列贷款分类中,不属于按照贷款用途划分的是()。
履行出资人职责的机构进行的下列行为,符合法律规定的有()。
下列方法中需要进行成本还原的是()。
管理思想演进的主要线索有()。
强调“扩大高等教育人学途径,加快培养各种专门人才”,“调整高等教育课程内容和结构”,“加强和改进高等教育管理,特别是要加强高校内部专业化的管理,提高教学和科研水平,以承担更多的社会和经济课题”,“开辟更多的奖学金和助学金途径,促进学生学习”的是
Despite(1)thatalcoholicbeveragesmay(2),aleadingmedicalexpertisadvising:don’t(3)justyet.Anybodywho’sever
最新回复
(
0
)