首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2019-08-15
65
问题
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
选项
A、O(nlog
2
n)
B、O(log
2
n)
C、O(n)
D、O(n
2
)
答案
A
解析
此题考查的知识点是各类排序的效率。理论上可以证明,对于基于关键字之间比较的分类,无论用什么方法都至少需要进行log
2
(n!)次比较。
由Stirling公式可知,log≈(n!)≈nlog
2
n一1.44n+O(log
2
n),所以基于关键字比较的分类时间的下界是D(nlog≈n)。因此不存在时间复杂性低于此下界的基于关键字比较的分类。应选A。
转载请注明原文地址:https://kaotiyun.com/show/QdCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
苏联实行新经济政策和美国推行罗斯福新政的相似点是()。①面临极为困难的经济形势②国家颁布政策法令强制干预经济③最主要内容是调整和复兴工业④通过发展商品生产来恢复农业
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,
在一个HDLC帧的数据中,如果出现了000111111011这样的流,请问发送到信道上它将会变成()。
若干个等待访问磁盘者依次要访问的柱面为20,44,40,4,80,12,76,假设每移动一个柱面需要3毫秒时间,移动臂当前位于40号柱面,请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。(1)先来先服务算法;(2)最短寻找时间
[*]对应的微指令如下:ADD01XX1010000010XX10010000XX1001001001MOV00XX10100010XX1101001001
在集中式总线仲裁中,()方式响应时间最快。
关于分页系统,回答下列问题:(1)在页表中,哪些数据项是为实现换页而设置的?(2)设某系统为每个作业进程分配3个内存块,某作业进程在运行访问中的轨迹为1,4,3,1,6,8,1,且每一页都是按请求装入的。问:先进先出页面置换算法(FIF
对下列4个序列用快速排序方法进行排序,以序列的第1个元素为基准进行划分。在第1趟划分过程中,元素移动次数最多的是()。
给定页面请求序列RS=cadbebabcd,页框为4,起始为空,写出LRU页面置换过程。
随机试题
新斯的明最强的作用是
囊性淋巴管瘤的临床表现如下.除外()
关于糖原合酶的活性,下列论述中正确的是
治疗痰湿型癥瘕的主方是治疗痰湿型不孕的主方是
下列关于法律原则作用的说法中哪一项不能成立?()
递延资产是指不能全部计入当年损益,应当在以后年度内分期摊销的各项费用。()
2016年初某企业向税务机关报送2015年度企业所得税纳税申报表,表中填报的产品销售收入为700万元,减除成本、费用、税金后,利润总额为一15万元。应纳税所得额为一15万元。税务机关通知该企业委托税务师事务所进行所得税审计,否则税务机关将对其进行查账稽核。
(1989年)设抛物线y=aχ2+bχ+c过原点,当0≤χ≤1时,y≥0,又已知该抛物线与χ轴及直线χ=1所围成图形的面积为,试确定a,b,c,使此图形绕χ轴旋转一周而成旋转体的体积V最小.
下面是在HTML中使用“”标签编写的列表在浏览器中的显示效果,列表内容应放置在_________标记内。
Themostpressingnuclearenergyissueisthedisposalofnuclearwaste.Evenifallthereactorsinexistencewerecompletelys
最新回复
(
0
)