首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2019-01-30
51
问题
基于比较方法的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/uaRi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
论述东欧剧变的原因和性质。
阅读材料，回答以下问题：一、大清帝国之皇统，万世不易。二、皇帝神圣，不可侵犯。三、皇帝权以宪法规定为限。四、皇帝继承之顺序，于宪法规定之。五、宪法由资政院起草议决，皇帝颁布之。六、宪政改正提案权，属于国会。七、上院议员，由国民于法定特别资格公选之。八、总
清廷实行厘金制度的时间是（）。
下列口号中，最能反映五四运动性质的是()。
1854年，英国外交大臣致函英国驻华公使说：“为了适应外商对农业产品已增加了的需要，新的贸易市场尚待开辟。”1856年，法国外长则指令法国驻华代办强调“商业关系的推广”，并强调“这是一个关系到至高无上权益的问题”。这说明()。
若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其层次序列为()。
下面关于进程的叙述中，正确的是()。
在Windows操作系统中支持FAT32文件系统，一个文件的物理结构是用文件分配表FAT来表示的，在FAT32中，文件分配表每个表项占32位。如果某分区为FAT32磁盘文件系统，每簇8扇区，扇区的大小为512字节，则该分区最大可为多少字节?每个FAT表占用
一个磁盘有N个磁道，寻道时每移过一个磁道耗时T秒，文件相邻的数据块在磁盘上存放的位置平均相隔13个磁道，磁盘旋转延时平均R秒，每个存储块的传输时间为P秒，在这种情况下，传输100个数据块需要的时间是()。
假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享卡H同的后缀存储空间。例如，“loading”和“being”的存储映像如下图所示。设str1和m2分别指向两个单词所在单链表的头结点，链表结点结构为请设计一个时间上尽可能高效的算法，找出
随机试题
遇雨、雾、霾等能见度不良天气时，工程船舶和施工区域应显示规定的信号，必要时应停止航行或作业。()
滤过分数是指()
将标准深度100英尺4等份，每一等份的价值占路线价的比例分别为40%、30%、20%、10%的路线法则是()。
()是指已经运到企业，并己验收入库的各种原材料、半成品或商品。
培育和规范劳动力市场要()。
替代品是指两种商品互相配合来共同满足同一种需求，它们之间是相互补充的。()
根据下面材料回答下列题。2013年1～11月份．商品房销售面积110807万平方米，同比增长20．8％，增长速度比1～10月份回落1个百分点：其中，住宅销售面积增长21．3％，办公楼销售面积增长26．6％，商业营业用房销售面积增长12．1％。商品
Theconceptofpersonalchoiceconcerninghealthisimportantbecause______.Toknowinglyallowoneselftopursueunhealthyh
Islanguage,likefood,abasichumanneedwithoutwhichachildatacriticalperiodoflifecanbestarvedanddamaged?【C1】___
Apioneeringheadteacheriscallingforallsecondaryschoolstofollowhisleadandstartclassesat11am,allowingteenagers
最新回复
(
0
)
