首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2023-02-06
52
问题
基于比较方法的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
学硕统考专业
相关试题推荐
下列选项中，影响教育功能发挥的最直接因素是()。
培养正确的集体舆论的方法是()。
党的十九大报告指出，到中华人民共和国成立一百年时，基本实现现代化，把我国建设成社会主义现代化国家。综合分析国际国内形势和我国发展条件，从2020年到本世纪中叶可以分为两个阶段来安排，这两个阶段分别是()。
一位老师认为，儿童就像一张白纸，如果给他足够的时间和资源，他能将儿童培养成任何你想要其成为的人。这位老师的观点与教育学家()的教育主张相似。
某学者认为，人类的体力、情绪、智力自出生日起分别以22天、28天、33天为周期开始往复循环变化，前半个周期是“高潮期”，后半个周期是“低潮期”。根据该学者的观点，我们过公历生日时，体力、情绪和智力同时处于“高潮期”的最小年龄是：
2020年末，全国共有艺术表演团体17581个，从业人员43．69万人，其中各级文化和旅游部门所属艺术表演团体2060个，从业人员10．75万人。2020年，全国文化和旅游部门所属艺术表演团体共组织政府采购公益演出13．38万场，比上年下降14．9％；观众
下图右侧四个选项中，对左侧零件的四个立面呈现有错误的一项是：
根据联合国官网，联合国大会将“青年”定义为年龄介于15岁至24岁之间(含15岁和24岁)的那些人。根据中共中央、国务院近日印发的《中长期青年发展规划(2016—2025年)》所指的，“青年”年龄范围是14～35周岁。以下各项说法能够从题干中推出的是：
某军用加油站的储油罐装有甲、丙两条输入管和乙、丁两条输出管。要注满储油罐，单开甲管需要3天，单开丙管需要5天。要放空储油罐，单开乙管需要4天，单开丁管需要6天。现在储油罐内装有1/6罐油，如果按甲、乙、丙、丁的顺序轮流各开1天，那么注满储油罐需要(
某次会议邀请4所高校每所各2位学者做报告。在某日上午、下午和晚上的三个时间段分别安排3位、3位和2位学者依次做报告，且同一所高校的2位学者不安排在同一时间段内做报告。问：8人的报告次序有多少种不同的安排方式?
随机试题
脓性指头炎切开减压引流的指征是
有关系统论的描述正确的是
对健康定义的说法是除无躯体疾病外还要有
某女，停经56天，恶心呕吐1周，呕吐酸水或苦水，胸胁满闷，嗳气叹息，头晕目眩，口苦咽干，渴喜冷饮，便秘溲赤，舌红，苔黄燥，脉弦滑数。方宜
女，32岁。低热伴下腹痛1个月，大便3次／日。黄稀便，无脓血。腹部B超示右下腹部肠壁增厚。对诊断最有意义的检查是()
注册会计师C对N公司2006年度的财务报表进行审计，需要对助理人员的问题作出回答，请代为作出专业判断。
教师工作对象千差万别，这就要求教师要不断学习，不断反思，这说明教师是教学活动的()。
黏液质的人冷静、沉着、自制、踏实，但缺乏适当的教育就会导致()。
设A为m×n阶矩阵，且r(A)=m＜n，则()．
Scotland:aLandofWisdomInthe1740s,thefamousFrenchphilosopherVoltairesaid,"WelooktoScotlandforallourideas
最新回复
(
0
)
