首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2017-11-14
83
问题
基于比较方法的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/C3Ri777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
利玛窦与徐光启合作翻译的(),介绍了曾经流行于欧洲的欧几里得平面几何的系统理论,大大地丰富了中国古代几何学的内容。
下列有关《布列斯特和约》的说法中,错误的一项是()。
改革开放以来,乡镇企业的异军突起,其重要意义包括()①改变了公有制经济的主体地位②推动了农村产业结构的现代化进程③加快了农村的现代化进程④开辟了农民致富的新途径
19世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
下列关于第二三次科技革命的说法,不正确的是()。
中共八届九中全会提出的恢复和调整国民经济的方针是()。
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
地址总线A15~A0,其中A0是最低位。存储器地址空间为3000H~67FFH。其中3000H~4FFFH为RoM区,选用EPR()M芯片(4K×2);5000H~67FFH为RAM区,选用RAM芯片(2K×4)。(1)组成该存储器需用多少块EP
已知一个线性表为(38,25,74,63,52,48),假定采用H(K)=Kmod7计算散列地址进行散列存储,若利用线性探测的开放定址法处理冲突,则在该散列表上进行查找的平均查找长度为();若利用链地址法处理冲突,则在该散列上进行查找的平均查找长度
随机试题
天山:雪莲
______doesittakeyoutowashallthedishes?
胎粪的性状为
[1995年第022题]高层住宅电梯相邻两个停站的间距应当是:
下列不屈于组织结构模式内容的是()。
各级预算预备费的动用方案,由本级政府财政部门决定。()
下列关于自然人民事行为能力的表述中,错误的是()。
榜样的力量是无穷的,精神的力量是伟大的。50年来,在雷锋精神的感召下,涌现了一大批雷锋式的先进入物。“当代雷锋”郭明义就是其中的杰出代表。今天,无论是遍布全国的上百支郭明义爱心分队,还是郭明义微博上的680万“粉丝”,或是郭明义先进事迹报告会上泪流满面的听
求二元函数z=f(x,y)=x2y(4一x一y)在直线x+y=6,x轴与y轴围成的闭区域D上的最大值与最小值.
InthemonthofSeptember,inBritain,youmayseelargenumbersofbirds(1)_____onroofsandtelegraphwires.Thesebirdsare
最新回复
(
0
)