首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的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
)
