首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2019-08-15
49
问题
基于比较方法的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
学硕统考专业
相关试题推荐
赋税是我国古代国家宏观管理经济的重要手段。据此回答问题:西汉到北魏赋税制度的变化的基本趋势是()
中共八届九中全会提出的恢复和调整国民经济的方针是()。
假设系统的所有资源是同类型的,系统中的进程每次申请资源数最多1个,那么,下面列出的4种情况中,()可能发生死锁。情况序号系统中进程数资源总量
在一个HDLC帧的数据中,如果出现了000111111011这样的流,请问发送到信道上它将会变成()。
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
在4×100米接力赛中,4个运动员之间存在如下关系:运动员1跑到终点把接力棒交给运动员2;运动员2一开始处于等待状态,在接到运动员1传来的接力棒后才能往前跑,他跑完100米后交棒给运动员3;运动员3也只有接到运动员2传来的接力棒后才能往前跑,他跑完100米
某计算机采用Cache一主存一磁盘三级存储系统。Cache的访问时间为t1ns,命中率为p1;若Cache未命中,CPU需直接访问主存,访问时间为t2ns,主存命中率为p2;若所需数据字不在主存中,则访问主存未命中、将包含所需数据字的磁盘数据块装入主存共需
若二叉树的前序序列为DABCEFG,中序序列为BACDFGE,则其层次序列为()。
给定页面请求序列RS=cadbebabcd,页框为4,起始为空,写出LRU页面置换过程。
随机试题
两个或多个点、线及平面的投影,重合在同一投影面上时,称为
浆细胞的特征是
下列哪个部分的上皮由单层柱状上皮构成
A、溃疡呈环形与肠的长轴垂直B、溃疡呈长椭网形与肠的长轴平行C、溃疡呈烧瓶状口小底大D、溃疡边缘呈堤状隆起E、溃疡表浅呈地图状肠伤寒的肠溃疡特征是
冠心病病人血压为80/60minHg,心尖部第一心音强弱不等;心电图示心房率慢于心室率,QRS波增宽为0.12秒,可见心室夺获和室性融合波。诊断为
甲承包经营某矿井采矿业务。甲为了降低采矿成本,提高开采量,便动员当地矿工和村民将子女带到矿井上班,并许诺给他们的子女高工资。矿工和村民纷纷将他们的子女带到矿井上班,从事井下采矿作业,其中有二十余人为10~16周岁的未成年人。后因甲所承诺的高工资未兑现,二十
对于个人风险承受能力评估方法中的定性方法和定量方法,下列说法正确的是()。
甲企业将原值70万元的房产评估作价80万元投资乙企业,乙企业办理产权登记后又将该房产以每年30万元的价格出租给丙企业,当地契税税率3%,则下列说法正确的有()。
下列有关公务员行为的说法中正确的是()。
推恩令
最新回复
(
0
)