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

admin2019-08-15 69

问题基于比较方法的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)，所以基于关键字比较的分类时间的下界是D(nlog≈n)。因此不存在时间复杂性低于此下界的基于关键字比较的分类。应选A。

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

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

计算机408

学硕统考专业

相关试题推荐

赋税是我国古代国家宏观管理经济的重要手段。据此回答问题：西汉到北魏赋税制度的变化的基本趋势是()
苏联实行新经济政策和美国推行罗斯福新政的相似点是()。①面临极为困难的经济形势②国家颁布政策法令强制干预经济③最主要内容是调整和复兴工业④通过发展商品生产来恢复农业
《中国国民党改组宣言》发表的时间是()。
(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，
如下图所示为一个网络连接的示意图，主机1到主机2采用了SLIP网络连接，SLIP网络可以传输的最大数据段是296字节，主机2和主机3使用了以太网连接。请问：(1)为了使IP不分片，主机1可以在TCP包中承载多少数据?(2)主机3可以在TCP包中承载多
在4×100米接力赛中，4个运动员之间存在如下关系：运动员1跑到终点把接力棒交给运动员2；运动员2一开始处于等待状态，在接到运动员1传来的接力棒后才能往前跑，他跑完100米后交棒给运动员3；运动员3也只有接到运动员2传来的接力棒后才能往前跑，他跑完100米
已知某CPU有16根地址线、8根数据线，并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片：1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干，如下图所
在下列排序方法中不需要对排序码进行比较就能进行排序的是()。
一个磁盘有N个磁道，寻道时每移过一个磁道耗时T秒，文件相邻的数据块在磁盘上存放的位置平均相隔13个磁道，磁盘旋转延时平均R秒，每个存储块的传输时间为P秒，在这种情况下，传输100个数据块需要的时间是()。

随机试题

A、ThemanalreadyhasplansforSundaynight.B、Thewomanshoulddecidewheretoeat.C、Thewomanshouldaskherbrotherforas
为了测定小儿麻痹症后遗症患者的臀中肌肌力，下列哪项试验是最正确的
患者女性，52岁，二尖瓣关闭不全病史15年，近日出现心悸，胸闷，行PDE检查显示重度二尖瓣反流。该患者心脏杂音的特点是
关于桥梁振型测定试验，以下描述正确的有()。
制定工程项目计划的主要步骤，其先后顺序是()。(1)把工程项目范围详细划分为各个工作包(2)进行资源消耗和评审(3)清晰地定义工程项目目标(4)确定质量检查评审的关键节点和质量检查
实现会计电算化后,会计数据的处理流程依旧和手工会计核算基本相同。()
企业销售商品时，销售收入确认的条件包括()。
甲区位于某市东南部，辖区面积210．22平方公里，共辖8个街道，户籍人口39．5万，登记外来人口42．5万。甲区公安分局情报中心对一周警情(2017年7月14日14时至7月21日14时)进行了统计分析。本周共接有效警情1591起，环比上升0．76％。其中，
我国横断山脉是具有国际意义生物多样性的关键地区，横亘()。
下列著作按照出现的先后顺序排列正确的是()。

最新回复(0)

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

计算机408

学硕统考专业

赋税是我国古代国家宏观管理经济的重要手段。据此回答问题：西汉到北魏赋税制度的变化的基本趋势是()

苏联实行新经济政策和美国推行罗斯福新政的相似点是()。①面临极为困难的经济形势②国家颁布政策法令强制干预经济③最主要内容是调整和复兴工业④通过发展商品生产来恢复农业

《中国国民党改组宣言》发表的时间是()。

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

已知某CPU有16根地址线、8根数据线，并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片：1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干，如下图所

在下列排序方法中不需要对排序码进行比较就能进行排序的是()。

一个磁盘有N个磁道，寻道时每移过一个磁道耗时T秒，文件相邻的数据块在磁盘上存放的位置平均相隔13个磁道，磁盘旋转延时平均R秒，每个存储块的传输时间为P秒，在这种情况下，传输100个数据块需要的时间是()。

A、ThemanalreadyhasplansforSundaynight.B、Thewomanshoulddecidewheretoeat.C、Thewomanshouldaskherbrotherforas

为了测定小儿麻痹症后遗症患者的臀中肌肌力，下列哪项试验是最正确的

患者女性，52岁，二尖瓣关闭不全病史15年，近日出现心悸，胸闷，行PDE检查显示重度二尖瓣反流。该患者心脏杂音的特点是

关于桥梁振型测定试验，以下描述正确的有()。

制定工程项目计划的主要步骤，其先后顺序是()。(1)把工程项目范围详细划分为各个工作包(2)进行资源消耗和评审(3)清晰地定义工程项目目标(4)确定质量检查评审的关键节点和质量检查

实现会计电算化后,会计数据的处理流程依旧和手工会计核算基本相同。()

企业销售商品时，销售收入确认的条件包括()。

我国横断山脉是具有国际意义生物多样性的关键地区，横亘()。

下列著作按照出现的先后顺序排列正确的是()。