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

admin2019-01-30 70

问题基于比较方法的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://www.kaotiyun.com/show/uaRi777K

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

计算机408

学硕统考专业

相关试题推荐

首次提出“长期共存，互相监督”观念的是在文件()中。
明朝灭亡后，以下南明小朝廷存在的先后顺序是()。①绍武政权②永历政权③隆武政权④弘光政权
1543年，发表了解剖学专著《人体结构》的是()。
火的使用，是人类在征服自然的进程中所取得的伟大成果。人类开始使用天然火是在()。
中国抗战在世界反法西斯战争中的作用。
20世纪50年代到70年代初，西欧国家通过有效的社会经济政策，维持了经济相对稳定和持续发展。这些政策主要包括()①加强对经济的宏观管理②废除生产关系中封建落后因素③发展高科技和新兴产业④进行社会改革，稳定社会
在请求页式系统中，一程序的页面走向(访问串或引用串)为2，3，4，5，2，3，6，2，3，4，5，6，设分配给该程序的存储块数为m。试分别计算m=3和m=4时，FIFO和LRU两种替换算法的缺页(页故障)数，并给出：结果说明了什么?
一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。
一个SPOOUNG系统由输入进程I、用户进程P、输出进程O、输入缓冲区、输出缓冲区组成。进程I通过输入缓冲区为进程P输入数据，进程P的处理结果通过输出缓冲区交给进程O输出。进程间数据交换以等长度的数据块为单位，这些数据块均存储在同一个磁盘上，因此，SPOO
下列关于客户／服务器模型的描述中，错误的是()。　Ⅰ客户端和服务器必须都事先知道对方的地址，以提供请求和服务　ⅡHTTP基于客户／服务器模型，客户端和服务器端的默认端口号都是80Ⅲ浏览器显示的内容来自服务器

随机试题

“十年树木，百年树人”体现的教师劳动特点是()。
下列诗句出自《古诗十九首》的是【】
腹腔穿刺抽出血性液体的疾病是
患儿，男。生后半个月发现左颈部包块，较硬，头向左偏，下颌转向右侧，6个月后颈部包块开始变小，面部不对称，在医院诊为先天性肌性斜颈，手术最佳年龄
以下哪种休克的治疗最适用于使用阿托品
在传染过程中，隐性感染增加时，其流行病学意义在于
在IP协议中用来进行组播的IP地址是()地址。
小学生创新发展的特点：(1)由（　　）创造向（　　）创造过渡；(2)由（　　）创造力向（　　）创造力过渡。
一、注意事项1．本卷总分100分，限时150分钟，其中阅读给定资料参考时限为40分钟。2．请仔细阅读给定的资料内容，然后按照后面提出的“作答要求”作答。二、给定资料1．2006年1月17日，一个类似美国“水门”事件中“深喉”的人
下列关于突触前抑制特点的描述，正确的是

最新回复(0)

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

计算机408

学硕统考专业

首次提出“长期共存，互相监督”观念的是在文件()中。

明朝灭亡后，以下南明小朝廷存在的先后顺序是()。①绍武政权②永历政权③隆武政权④弘光政权

1543年，发表了解剖学专著《人体结构》的是()。

火的使用，是人类在征服自然的进程中所取得的伟大成果。人类开始使用天然火是在()。

中国抗战在世界反法西斯战争中的作用。

20世纪50年代到70年代初，西欧国家通过有效的社会经济政策，维持了经济相对稳定和持续发展。这些政策主要包括()①加强对经济的宏观管理②废除生产关系中封建落后因素③发展高科技和新兴产业④进行社会改革，稳定社会

在请求页式系统中，一程序的页面走向(访问串或引用串)为2，3，4，5，2，3，6，2，3，4，5，6，设分配给该程序的存储块数为m。试分别计算m=3和m=4时，FIFO和LRU两种替换算法的缺页(页故障)数，并给出：结果说明了什么?

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

下列关于客户／服务器模型的描述中，错误的是()。 Ⅰ客户端和服务器必须都事先知道对方的地址，以提供请求和服务 ⅡHTTP基于客户／服务器模型，客户端和服务器端的默认端口号都是80Ⅲ浏览器显示的内容来自服务器

“十年树木，百年树人”体现的教师劳动特点是()。

下列诗句出自《古诗十九首》的是【】

腹腔穿刺抽出血性液体的疾病是

患儿，男。生后半个月发现左颈部包块，较硬，头向左偏，下颌转向右侧，6个月后颈部包块开始变小，面部不对称，在医院诊为先天性肌性斜颈，手术最佳年龄

以下哪种休克的治疗最适用于使用阿托品

在传染过程中，隐性感染增加时，其流行病学意义在于

在IP协议中用来进行组播的IP地址是()地址。

小学生创新发展的特点：(1)由（ ）创造向（ ）创造过渡；(2)由（ ）创造力向（ ）创造力过渡。

下列关于突触前抑制特点的描述，正确的是

下列关于客户／服务器模型的描述中，错误的是()。　Ⅰ客户端和服务器必须都事先知道对方的地址，以提供请求和服务　ⅡHTTP基于客户／服务器模型，客户端和服务器端的默认端口号都是80Ⅲ浏览器显示的内容来自服务器　

小学生创新发展的特点：(1)由（　　）创造向（　　）创造过渡；(2)由（　　）创造力向（　　）创造力过渡。