首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2017-01-04
43
问题
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
选项
A、O(nlog
2
n)
B、O(log
2
n)
C、O(n)
D、D(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://jikaoti.com/ti/g6fjFFFM
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
中国古代史分期问题的焦点有哪些?简述其代表人物及思想。(兰州大学2013年中国史基础真题)
《关于建国以来党的若干历史问题的决议》的主要内容及其意义。
1956年，苏共二十大后，匈牙利大党员和群众强烈要求克服个人崇拜，扩大民主，实行经济改革，一些由知识分子、大学生和干部组成的社团组织纷纷成立，其中最有影响者是()。
下列不是苏俄实行战时共产主义政策原因的是()。
关于中世纪西欧城市发展状况，叙述正确的是()。①城市取得自由或自治，一般以赎买为手段。②城市的自由和自治，一般以封建主或国王颁发的特许证书为凭据。③有的城市集体为封君服军役，并履行封臣的其他义务。④城市可视为
在下列四本部书中有可能记载“甘薯所在，局面便有半年之粮，民间渐次广种”一语的只能是()。
高度为4的4阶B树最多可容纳()个关键字(根是第1层)。
若一个栈的输入序列为1，2，3…n，输出序列的第一个元素是i，则第j个输出元素是()。
已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归且不用栈来完成?请简述原因。
某计算机的主存地址空间大小为256MB，按字节编址。指令Cache和数据Cache分离，均有8个Cache行，每个Cache行大小为64B，数据Cache采用直接映射方式。现有两个功能相同的程序A和B，其伪代码如下：假定int类型数据用32位补码表示，程序
随机试题
Ilikedlettersonwhichtheirhandwritingwasrushedandslightlyillegible,becauseifIhadtroubledecipheringthehandwriti
机动车仪表板上（如图所示）这个符号表示什么？
在某一操作条件下，管线的实际输气量为28×104m3／d，在该条件下计算的理论通过量为35×104m3／d，该管线目前运行状况()。
X线片上成人脊柱结核和脊柱肿瘤的主要鉴别点是
血容量不足时中心静脉压往往低于多少cmH2O(1cmH2O＝0.098kPa)
下列关于债券型理财产品的风险的说法，不正确的是()。
ABC会计师事务所接受了甲公司2017年度财务报表的审计业务，并指派A注册会计师担任项目合伙人。甲公司为酿酒行业的上市公司，从事畅饮牌系列酒的酿造与销售，产品分为高、中、低三个档次。存货主要包括粮谷、甘薯干和罐装酒，其中粮谷和甘薯干贮存在8个简易棚内，罐装
【2015广西】人发展的顺序性要求教育根据人发展的成熟机制，抓住发展的关键期，以促进其发展。()
在窗体上画两个文本框，其名称分别为Text1和Text2，然后编写如下程序：PrivateSubForm_Load()Text1．Text=””：Text2．Text=""：Text1．SetFocusEndSub
WhenwethinkofHollywood—atermIuselooselytodescribeAmericanmovieproductioningeneral,notsimplyfilmsmadeinLos
最新回复
(
0
)
