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

admin2017-01-04 36

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

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

答案A

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

转载请注明原文地址:https://jikaoti.com/ti/g6fjFFFM

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

计算机408

学硕统考专业

相关试题推荐

简述从十月革命胜利到第二次世界大战爆发前夕苏俄(苏联)与主要资本主义国家关系演变的基本情况。
1901年6月，发表《立宪法议》，首先提出君主立宪要求的是()。
十六国时期的历史，可以划分为前后两个时期，其分界线是()。
阅读下列史料，并回答问题：在琶勒尼斯(注：地名)一役获胜后，他(庇西特拉图)便占领政府，并解除人民武装；现在他已能稳定地握住僭主政权，并且取得那克索斯。以吕格达密斯为统治者。他解除人民武装的方法是这样的：他在塞修斯庙举行了一个武装的阅兵式，同时举行一次民
在下列哪个条约中，最先出现了片面最惠国待遇?()
在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。
一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。
A、1243B、4312C、2134D、3214D图的BFS遍历。D选项，首先访问结点3，与3邻接的结点4、2都未曾访问过，故3后面因该为2、4(或4、2)，故D错。
以数组Data[m+1]作为循环队列SQ的存储空间，front为头指针，rear为队尾指针，则执行出队操作的语句是()。
某计算机的主存地址空间大小为256MB，按字节编址。指令Cache和数据Cache分离，均有8个Cache行，每个Cache行大小为64B，数据Cache采用直接映射方式。现有两个功能相同的程序A和B，其伪代码如下：假定int类型数据用32位补码表示，程序

随机试题

一般认为职业是人们常规谋生的手段，而专业是对公众期待的责任有公开承诺的职业团体。以下对医学专业叙述不正确的有()。
血管网织细胞瘤病理分类不包括下列哪项
不承重侧模拆除时混凝土强度应()。
根据下面材料，回答问题。下列说法正确的是()。
在比较讲授法和讨论法的教学效果时，教师分别选用两个班级，一班采用讲授法，一班运用讨论法，两班学生在智力、学业基础等方面尽量保持均衡，期末时测量其成绩差异。这种教育研究方法属于()。
新中国建立后的土地改革政策与过去的主要不同是()。
公共行政管理活动所产生的符合国家意志和人民要求的行政成果是指()。
设L是一条平面曲线，其上任意一点P(x，y)(x＞0)到坐标原点的距离，恒等于该点处的切线在y轴上的截距，且L经过点(1/2，0)．求L位于第一象限部分的一条切线，使该切线与L及两坐标轴所围图形的面积最小．
一条指令的执行可划分成取值，分析和执行三个部分，不同的部分由不同自由独立的硬件完成。设每一指令完成取值，分析和执行三部分的时间分别为1ns，3ns，1ns现有100条指令，若顺序执行这些指令需要(57)；若采用流水方式执行这些指令则需要(58)。
Educationistooimportanttotake【B1】______.Whenpeopletakeanythingtooseriously,theyputonblinders,whichcausethemto

最新回复(0)

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

计算机408

学硕统考专业

简述从十月革命胜利到第二次世界大战爆发前夕苏俄(苏联)与主要资本主义国家关系演变的基本情况。

1901年6月，发表《立宪法议》，首先提出君主立宪要求的是()。

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

在下列哪个条约中，最先出现了片面最惠国待遇?()

在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。

A、1243B、4312C、2134D、3214D图的BFS遍历。D选项，首先访问结点3，与3邻接的结点4、2都未曾访问过，故3后面因该为2、4(或4、2)，故D错。

以数组Data[m+1]作为循环队列SQ的存储空间，front为头指针，rear为队尾指针，则执行出队操作的语句是()。

一般认为职业是人们常规谋生的手段，而专业是对公众期待的责任有公开承诺的职业团体。以下对医学专业叙述不正确的有()。

血管网织细胞瘤病理分类不包括下列哪项

不承重侧模拆除时混凝土强度应()。

根据下面材料，回答问题。下列说法正确的是()。

在比较讲授法和讨论法的教学效果时，教师分别选用两个班级，一班采用讲授法，一班运用讨论法，两班学生在智力、学业基础等方面尽量保持均衡，期末时测量其成绩差异。这种教育研究方法属于()。

新中国建立后的土地改革政策与过去的主要不同是()。

公共行政管理活动所产生的符合国家意志和人民要求的行政成果是指()。

设L是一条平面曲线，其上任意一点P(x，y)(x＞0)到坐标原点的距离，恒等于该点处的切线在y轴上的截距，且L经过点(1/2，0)．求L位于第一象限部分的一条切线，使该切线与L及两坐标轴所围图形的面积最小．

Educationistooimportanttotake【B1】______.Whenpeopletakeanythingtooseriously,theyputonblinders,whichcausethemto