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

admin2019-05-20 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)。所以基于关键字比较的分类时间的下界是O(nlog₂n)。因此不存在时间复杂性低于此下界的基于关键字比较的分类。应选A。

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

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

计算机408

学硕统考专业

相关试题推荐

下列内容，哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张，从经济上瓜分世界
世界近代史上，世界经济发展经历了两次大的飞跃，即第一次工业革命和第二次工业革命。阅读下面两段材料，回答问题：材料一工业革命的主角——蒸汽机，是经验和科学相结合的产物。科学对工业革命的发展做出重大贡献。工场手工业的生产，主要依靠以人力和经
西周前期，曾先后向东、南和西三个方向扩张，其中向南扩张主要发生在()
国民党政府宣布民盟为“非法团体”，民盟总部被迫解散的时间是()。
武则天时期，为了管理天山以北的广大区域而设立了()。
1854年，英国外交大臣致函英国驻华公使说：“为了适应外商对农业产品已增加了的需要，新的贸易市场尚待开辟。”1856年，法国外长则指令法国驻华代办强调“商业关系的推广”，并强调“这是一个关系到至高无上权益的问题”。这说明()。
高度为7的AVL树最少有()个结点。
假定某采用页式虚拟存储管理的计算机系统中，主存储器容量为1GB，被分为262144块物理块，物理块号为0，1，2，……，262143。某进程的地址空间占4页，逻辑页号为0，1，2，3，被分配到主存储器的第20，45，101，58号物理块中。回答：
某模型机的通路结构如图7—1所示，用寄存器传送语句(如PC→MAR)，拟出下列指令从读取到执行的完整流程。　　(1)数据传送指令MOVX(R0)，Y(R1)，源和目的操作数地址均采用变址寻址，第1个参数X为源操作数的形式地址，第2个参数为目的操作数的形
一个有50个路由器的网络，采用基于距离一向量的路由选择算法，路由表的每个表项长度为6B，每个路由器都有3个邻接路由器，每秒与每个邻接路由器交换1次路由表，则每条链路上由于路由器更新路由信息而耗费的带宽为()。

随机试题

识别病毒在细胞内增殖的指标有：细胞形态改变、细胞分裂增殖、红细胞吸附、空斑形成单位、干扰现象和细胞培养液pH的改变。()
有以下程序：#include＜stdio．h＞#definef(x)x*x*xmain(){inta=3，s，t；s=f(a+1)；t=f((a+1))；printf("％d，％d＼n"，
下列哪种药物与消化性溃疡病因无关
用人单位应当保障职业病防治所需的资金投入，不得挤占、挪用，并对因资金投入不足导致的后果承担责任。()
某破产企业有9位债权人，债权总额为1100万元。其中债权人甲的债权额为300万元，由破产企业的房产作抵押。当债权人会议讨论和解协议草案时，下列情形中，可以通过的是()。
导游词通常由()等部分组成。
生活中我们发现，将两个鸡蛋相碰，往往只有一个被击破，则下列关于鸡蛋在相互碰撞时的受力情况的说法正确的一项是()。
某小组有四位男性和两位女性，六人围成一圈跳集体舞，不同的排列方法有多少种?()
无限制潜艇战
WhichofthefollowingsentencesisINCORRECT?

最新回复(0)

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

计算机408

学硕统考专业

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

西周前期，曾先后向东、南和西三个方向扩张，其中向南扩张主要发生在()

国民党政府宣布民盟为“非法团体”，民盟总部被迫解散的时间是()。

武则天时期，为了管理天山以北的广大区域而设立了()。

高度为7的AVL树最少有()个结点。

一个有50个路由器的网络，采用基于距离一向量的路由选择算法，路由表的每个表项长度为6B，每个路由器都有3个邻接路由器，每秒与每个邻接路由器交换1次路由表，则每条链路上由于路由器更新路由信息而耗费的带宽为()。

识别病毒在细胞内增殖的指标有：细胞形态改变、细胞分裂增殖、红细胞吸附、空斑形成单位、干扰现象和细胞培养液pH的改变。()

有以下程序：#include＜stdio．h＞#definef(x)x*x*xmain(){inta=3，s，t；s=f(a+1)；t=f((a+1))；printf("％d，％d＼n"，

下列哪种药物与消化性溃疡病因无关

用人单位应当保障职业病防治所需的资金投入，不得挤占、挪用，并对因资金投入不足导致的后果承担责任。()

某破产企业有9位债权人，债权总额为1100万元。其中债权人甲的债权额为300万元，由破产企业的房产作抵押。当债权人会议讨论和解协议草案时，下列情形中，可以通过的是()。

导游词通常由()等部分组成。

生活中我们发现，将两个鸡蛋相碰，往往只有一个被击破，则下列关于鸡蛋在相互碰撞时的受力情况的说法正确的一项是()。

某小组有四位男性和两位女性，六人围成一圈跳集体舞，不同的排列方法有多少种?()

无限制潜艇战

WhichofthefollowingsentencesisINCORRECT?

有以下程序：#include＜stdio．h＞#definef(x)xxxmain(){inta=3，s，t；s=f(a+1)；t=f((a+1))；printf("％d，％d＼n"，