首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2019-05-20
35
问题
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
选项
A、O(nlog
2
n)
B、O(log
2
n)
C、O(n)
D、O(n
2
)
答案
A
解析
此题考查的知识点是各类排序的效率。理论上可以证明,对于基于关键字之间比较的分类,无论用什么方法都至少需要进行log
2
(n!)次比较。
由Stirling公式可知,log
2
(n!)≈nlog
2
n一1.44n+O(log
2
n)。所以基于关键字比较的分类时间的下界是O(nlog
2
n)。因此不存在时间复杂性低于此下界的基于关键字比较的分类。应选A。
转载请注明原文地址:https://kaotiyun.com/show/t2Ci777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列说法中,全部符合历史事实的是()。①阿拉伯阿拔斯王朝的首都是麦地那②穆罕默德死后,他的继承人改称为哈里发,第三任哈里发奥斯曼时期,部分下层莫斯林组建了军事民主派,称为哈瓦立及派③阿拉伯人灭亡了具有1200年历史的波斯帝国的战役是雅穆克
唐朝对外关系呈现出前所未有的盛况,其原因不包括()
《论十大关系》
洋务运动期间,军事企业主要采取的方式是()。
到1869年为止,人类已发现了多少种化学元素()。
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用getev
操作系统采用页式存储管理方法,要求()。
循环队列用数组A[0..m~1]存放其元素值,已知其头尾指针分别为front和rear,则当前元素个数为()。
假设有k个关键字互为同义词,若用线性探查法把这k个关键字存入,至少要进行的探查次数是()。
二维数组A的每个元素是由6个字符组成的串,其行下标i=0,1…….,8,列下标j=1,2……,10。设每个字符占一个字节。若A按行先存储,元素A[8,5]的起始地址与当A按列先存储时起始地址相同的元素是()。
随机试题
从艺术起源角度为艺术下定义的学说有________、______。
下列哪项对企业来说不属于技术环境()
多发性骨髓瘤CT检查主要目的是
下列选项中对无效合同特征的描述,说法正确的有()。
在借贷记账法下,借方表示资产增加、费用增加,以及负债及所有者权益的减少。 ( )
下列关于个人信用贷款的贷款对象说法正确的是()。
中国共产党发展历程中的历史伟业有()。
在下列选项中,不是算法一般应该具有的基本特征的是
在关系模型中,每一个二维表称为一个
Inthenext40years,thepercentageofpeopleintheUnitedStatesovertheageof65isexpectedtodouble.【C1】______theneeds
最新回复
(
0
)