首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2019-01-30
47
问题
基于比较方法的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
学硕统考专业
相关试题推荐
希腊化时代控制希腊半岛的是()。
17世纪英国资产阶级革命中,曾利用了古老文件同专制王权作斗争,这一古老文件是()。
阅读下面史料,回答问题:材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下:合众国525000吨;英帝国525000吨;法国175000吨;意大利175000吨;日本315000吨。
如下图所示为一个网络连接的示意图,主机1到主机2采用了SLIP网络连接,SLIP网络可以传输的最大数据段是296字节,主机2和主机3使用了以太网连接。请问:(1)为了使IP不分片,主机1可以在TCP包中承载多少数据?(2)主机3可以在TCP包中承载多
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址。(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构
大部分文件系统以硬盘作为文件存储器。某一个文件系统中,其磁盘物理块的大小为512B,有一个文件,包含了590个逻辑记录,每个记录占255B;其中,为检索方便,采用成组法存储,在每个物理块上只存放2个记录。,文件A在该文件目录中的位置如下图所示。
将要相互通信双方怎样进行建立TCP连接?在TCP报文段的首部巾只有端口号而没有IP地址,当TCP将其报文段交给IP层时,IP协议怎样知道目的TP地址呢?为什么把IP地址又称为“虚拟地址”,把TCP连接说成是“虚连接”?假没在建立连接时使用2次握手而非3次握
随机试题
依据《普通高中美术课程标准(2017年版2020年修订)》,必修课程和选择性必修课程学业水平考试的等级分为()。
甲企业以某专利技术向乙企业投资,该技术的重置成本为100万元,乙企业拟投入合营的资产重置成本为6000万元,甲企业无形资产成本利润率为400%,乙企业拟合营的资产原利润率为13%。要求:评估该项无形资产投资的利润分成率。
Therearesigns______restaurantsarebecomingmorepopularwithfamilies.
在某医院心内科的住院患者中,几天内突然发生多例医院感染,该现象属于
计算机X线摄影使用的辐射转换器是
体外抗菌活性最强的氟喹诺酮类药物是
下列个人收入,属于纳税人应按“劳务报酬所得”缴纳个人所得税的有()。
(2019年)下列有关科目的月末余额应列入资产负债表“在建工程”项目的是()。
求。
Ilattendsescamarades_________l"entréedumusée.
最新回复
(
0
)