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

admin2019-08-15 71

问题基于比较方法的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)所有事件的最早发生时间如下：Ve(1)=0Ve(2)==5Ve(3)=6Ve(4)=max{ve(2)+3，ve(3)+6}=12Ve(5)=max{ve(3)+3，ve(4)+3}=15Ve(6)=ve(4)+4=16Ve(7)=ve
假设系统的所有资源是同类型的，系统中的进程每次申请资源数最多1个，那么，下面列出的4种情况中，()可能发生死锁。情况序号系统中进程数资源总量
在一个HDLC帧的数据中，如果出现了000111111011这样的流，请问发送到信道上它将会变成()。
已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列
某机字长32位，总线数据线宽度是16位，一个总线周期占用4个时钟周期，总线时钟频率为10MHz，则总线带宽是()。
若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其层次序列为()。
在TELNET协议中，用户发送的命令采用TCP传输到服务器，在TCP的数据包中，需要把()符号位置移位，从而使服务器尽快响应命令。
一个磁盘有N个磁道，寻道时每移过一个磁道耗时T秒，文件相邻的数据块在磁盘上存放的位置平均相隔13个磁道，磁盘旋转延时平均R秒，每个存储块的传输时间为P秒，在这种情况下，传输100个数据块需要的时间是()。
采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是____。

随机试题

索引
某高血压患者，突发呼吸困难，不能平卧，双肺满布湿性啰音，测血压为32．0／16．0kPa(240／120mmHg)，宜选用下列哪种药物治疗
下述哪项不是急性胎儿窘迫的常见原因()
泥浆护壁钻孔灌注桩施工工艺流程中，“第二次清孔”的下一道工序是()。
慢性精神分裂症患者“社交退缩”的临床表现是()。
Womenoften【1】thatdatingislikeacattle【2】,andapaperjustpublishedinBiologyLettersbyThomasPolletandDanielNettle
Optimistsoutlivepessimists,anewstudyshows.Ofnearly100,000women【C1】______intheWomen’sHealthInitiative,thosewhoga
Childrenwhogriptheirpenstooclosetothewritingpointarelikelytobeatadisadvantageinexaminations,【31】______tothe
Ifthereisonethingscientistshavetohear,itisthatthegameisover.Raisedonthebeliefofanendlessvoyageofdiscove
Forthispart,youareallowed45minutestowriteacompositionentitledOnFabricatingAcademicCredentials.Youshouldwrite

最新回复(0)

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

计算机408

学硕统考专业

洋务运动时期，首批赴欧海军留学生派出的时间是()。

(1)所有事件的最早发生时间如下：Ve(1)=0Ve(2)==5Ve(3)=6Ve(4)=max{ve(2)+3，ve(3)+6}=12Ve(5)=max{ve(3)+3，ve(4)+3}=15Ve(6)=ve(4)+4=16Ve(7)=ve

假设系统的所有资源是同类型的，系统中的进程每次申请资源数最多1个，那么，下面列出的4种情况中，()可能发生死锁。情况序号系统中进程数资源总量

在一个HDLC帧的数据中，如果出现了000111111011这样的流，请问发送到信道上它将会变成()。

已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列

某机字长32位，总线数据线宽度是16位，一个总线周期占用4个时钟周期，总线时钟频率为10MHz，则总线带宽是()。

若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其层次序列为()。

在TELNET协议中，用户发送的命令采用TCP传输到服务器，在TCP的数据包中，需要把()符号位置移位，从而使服务器尽快响应命令。

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

采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是____。

索引

某高血压患者，突发呼吸困难，不能平卧，双肺满布湿性啰音，测血压为32．0／16．0kPa(240／120mmHg)，宜选用下列哪种药物治疗

下述哪项不是急性胎儿窘迫的常见原因()

泥浆护壁钻孔灌注桩施工工艺流程中，“第二次清孔”的下一道工序是()。

慢性精神分裂症患者“社交退缩”的临床表现是()。

Womenoften【1】thatdatingislikeacattle【2】,andapaperjustpublishedinBiologyLettersbyThomasPolletandDanielNettle

Optimistsoutlivepessimists,anewstudyshows.Ofnearly100,000women【C1】______intheWomen’sHealthInitiative,thosewhoga

Childrenwhogriptheirpenstooclosetothewritingpointarelikelytobeatadisadvantageinexaminations,【31】______tothe

Ifthereisonethingscientistshavetohear,itisthatthegameisover.Raisedonthebeliefofanendlessvoyageofdiscove

Forthispart,youareallowed45minutestowriteacompositionentitledOnFabricatingAcademicCredentials.Youshouldwrite