基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。

admin2019-05-20 54

问题基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。

选项 A、O(nlog₂n)
B、O(log₂n)
C、O(n)
D、O(n²)

答案A

解析此题考查的知识点是各类排序的效率。理论上可以证明，对于基于关键字之间比较的分类，无论用什么方法都至少需要进行log₂(n!)次比较。
由Stirling公式可知，log₂(n!)≈nlog₂n一1．44n+O(log₂n)。所以基于关键字比较的分类时间的下界是O(nlog₂n)。因此不存在时间复杂性低于此下界的基于关键字比较的分类。应选A。

转载请注明原文地址:https://kaotiyun.com/show/t2Ci777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

三国时期，魏、蜀、吴三国灭亡的历史顺序是()。
阅读下列材料，并结合所学知识回答问题：材料一重申粮食垄断和价格都是不可更改的，重申必须同粮食投机商进行无情斗争，同时责成每一者，必须在本法令公布后一周内，把超过播种田地和自己到下次收获前的定额消费量的全部余粮呈报交售，呈报的办法由粮
在西欧列强海外殖民扩张进程中，各国之间相互争夺海上霸权。18世纪末，英国在争霸中取得胜利的根本原因在于()
下列科技文化成就，产生于3世纪的是()。①刘徽提出计算圆周率的正确方法②贾思勰著《齐民要术》③钟繇把隶书转化为楷书④马钧发明翻车
阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。
下列内容，与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张，从经济上瓜分世界
设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为：MAX{从w到v的最短距离｜w属于V(G))如果v是有向图G中具有的最小偏心度的顶点，则称顶点v是G的中心点。
某计算机的CPU主频为500MHz，CPI为5(即执行每条指令平均需5个时钟周期)。假定某外设的数据传输率为0．5MB／s，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间
将要相互通信双方怎样进行建立TCP连接?在TCP报文段的首部中只有端口号而没有IP地址，当TCP将其报文段交给IP层时，IP协议怎样知道目的IP地址呢?为什么把IP地址又称为“虚拟地址”，把TCP连接说成是“虚连接”?假设在建立连接时使用2次握手而非3次握
大部分文件系统以硬盘作为文件存储器。某一个文件系统中，其磁盘物理块的大小为512B，有一个文件，包含了590个逻辑记录，每个记录占255B；其中，为检索方便，采用成组法存储，在每个物理块上只存放2个记录。，文件A在该文件目录中的位置如下图所示。

随机试题

比较贷款的合同利率，贷款的实际利率更能体现出该笔放款给银行带来的真实的报酬率。()
电子对效应
下列造成智齿阻生及发生冠周炎的病因中错误的是
下列何项不是急性盆腔炎的手术指征
公司的种类有()。
为获取充足的资金以偿还未来的某项债务，因此而使用的建立债券组合的策略称为多重支付负债下的免疫策略和现金流匹配策略。()
离婚诉讼中，无过错方有权请求损害赔偿的情形是()。
Wearenotconsciousoftheextentofwhichworkprovidesthepsychologicalsatisfactionthatcanmakethedifferencebetweena
VocationalSchoolsTheuniversitiesarenotabletomeetallthe【T1】______needsofthesocietyforfuture【T2】______.Vocati
Ofthetwokindsofballgames,I’dpreferbasketball______(well).

最新回复(0)

基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。

计算机408

学硕统考专业

三国时期，魏、蜀、吴三国灭亡的历史顺序是()。

在西欧列强海外殖民扩张进程中，各国之间相互争夺海上霸权。18世纪末，英国在争霸中取得胜利的根本原因在于()

下列科技文化成就，产生于3世纪的是()。①刘徽提出计算圆周率的正确方法②贾思勰著《齐民要术》③钟繇把隶书转化为楷书④马钧发明翻车

阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。

下列内容，与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张，从经济上瓜分世界

设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为：MAX{从w到v的最短距离｜w属于V(G))如果v是有向图G中具有的最小偏心度的顶点，则称顶点v是G的中心点。

比较贷款的合同利率，贷款的实际利率更能体现出该笔放款给银行带来的真实的报酬率。()

电子对效应

下列造成智齿阻生及发生冠周炎的病因中错误的是

下列何项不是急性盆腔炎的手术指征

公司的种类有()。

为获取充足的资金以偿还未来的某项债务，因此而使用的建立债券组合的策略称为多重支付负债下的免疫策略和现金流匹配策略。()

离婚诉讼中，无过错方有权请求损害赔偿的情形是()。

Wearenotconsciousoftheextentofwhichworkprovidesthepsychologicalsatisfactionthatcanmakethedifferencebetweena

VocationalSchoolsTheuniversitiesarenotabletomeetallthe【T1】______needsofthesocietyforfuture【T2】______.Vocati

Ofthetwokindsofballgames,I’dpreferbasketball______(well).

VocationalSchoolsTheuniversitiesarenotabletomeetallthe【T1】needsofthesocietyforfuture【T2】.Vocati