首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2019-01-30
44
问题
基于比较方法的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://jikaoti.com/ti/wUfjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
杜鲁门总统执政时期,针对美国国内问题提出的计划是()。
第一次国共合作采取了共产党员以个人身份加入国民党的党内合作方式,最早提出这种方式的是()。
抗日战争期间,日本将沦陷区的许多矿产业、钢铁业等交给日本公司管理,其名义是()。
下列有关《布列斯特和约》的说法中,错误的一项是()。
下列哪一项不是凯末尔世俗化改革的内容?()
8世纪中期,控制东自黑龙江,西到阿尔泰山广大地区的民族是()。
“全部政权归苏维埃”的口号的提出是在()。
阅读下面史料,回答问题:材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下:合众国525000吨;英帝国525000吨;法国175000吨;意大利175000吨;日本315000吨。
IP数据报的报文格式如下图所示。在没有选项和填充的情况下,报头长度域的值为()。
在下面的应用中,通常使用栈的是()。 Ⅰ递归调用Ⅱ括号匹配Ⅲ表达式求值
随机试题
毛泽东提出的“工农武装割据”的基本内容包括()
Marfan综合征的病变特点是
制作X线管阳极靶面的材料必须是
A.白细胞管型B.红细胞管型C.透明管型D.蜡样管型E.上皮细胞管型提示慢性肾小球肾炎晚期的是
A.经营性互联网药品信息服务B.非经营性互联网药品信息服务C.网上药品交易服务D.互联网药品信息服务E.互联网信息服务
跟单员应具备的素质有()。
ShoppinghabitsintheUnitedStareshavechangedgreatlyinthelastquarterofthe20thcentury.Earlyinthe1900smostAmeri
1.2018年年初,16万份调查问卷显示,84%的企业和居民认为,N省Y市营商环境有改善,制约营商环境的“最后一公里”正在被打通。“营商环境建设,必须从以供给侧为重点转向以需求侧为重点,企业需要什么环境,我们就打造什么样的环境。”Y市市委副书记、市长姜有
下列关于生活中数学现象的表述错误的是:()
GlobalwarmingcouldactuallychilldownNorthAmericawithinjustafewdecades,accordingtoanewstudythatsaysasuddenco
最新回复
(
0
)