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

admin2017-01-04 58

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

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

计算机408

学硕统考专业

相关试题推荐

【《关于正确处理人民内部矛盾的问题》】
“班禅额尔德尼”最早是由清朝的()皇帝敕封的。
隋唐科举制的进士科最先出现在()。
1908年安庆新军起义是由()领导的。
下列不是唐玄宗组织编撰的是()。
印度种姓制度中，处于被剥削被压迫地位的两个瓦尔那是()①婆罗门②刹帝利③首陀罗④吠舍
在一个HDLC帧的数据中，如果出现了000111111011这样的流，请问发送到信道上它将会变成()。
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的：ProcessPO：do{flag[0]=true；While(flag[1])；
由元素序列(27，16，75，38，51)构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)是()。
某主机的MAC地址为00．15．C5．C1．5E．28，IP地址为10．2．128．100(私有地址)。题47-a图是网络拓扑，题47-b图是该主机进行Web请求的1个以太网数据帧前80B的十六进制及ASCII码内容。请参考图中的数据回答以下问题。

随机试题

与痰饮形成关系不密切的脏腑是（　　）。
患者反复感染，出血2个月。检查：全血细胞减少，肝、脾、淋巴结肿大，骨髓象及淋巴结活检均发现异常组织细胞及多核巨组织细胞。其诊断是
根据国家赔偿法，单独提出赔偿请求的情况主要有哪些?(　　　)
下列关于法律制定的说法，不正确的为哪一个选项?()
刘某缺席会计人员继续教育培训的行为违背了提高技能的会计人员职业道德规范。提高技能是指会计人员通过学习、培训等手段提高职业技能已达到足够的专业胜任能力的活动。
增值税采用间接的计算方法，以商品货物的(　　)为计税依据。
音乐童话《龟兔赛跑》创作于20世纪60年代，它采用管弦乐的形式，加上简练的解说表现童话故事，深受孩子们的喜爱，其作者是史真荣。()
淬火效应原意为金属工件加热到一定温度后，浸入冷却剂(油、水等)中，经过冷却处理，工件的性能更好、更稳定。引申到教育学中，对长期受表扬头脑有些发热的学生，不妨设置一点小小的障碍，施以“挫折教育”，几经锻炼，其心理会更趋成熟，心理承受能力会更强；对于麻烦事或者
Theevolutioninpublicpolicyconcerningthemanufacture,saleandpossessionofsemiautomaticassaultweaponslikeAK-47s,AR-
YouwillhearaninterviewaboutGalapagosAdventureTourinEcuador.Asyoulisten,youmustanswerQuestions21to30bywriti

最新回复(0)

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

计算机408

学硕统考专业

【《关于正确处理人民内部矛盾的问题》】

“班禅额尔德尼”最早是由清朝的()皇帝敕封的。

隋唐科举制的进士科最先出现在()。

1908年安庆新军起义是由()领导的。

下列不是唐玄宗组织编撰的是()。

印度种姓制度中，处于被剥削被压迫地位的两个瓦尔那是()①婆罗门②刹帝利③首陀罗④吠舍

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

试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的：ProcessPO：do{flag[0]=true；While(flag[1])；

由元素序列(27，16，75，38，51)构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)是()。

某主机的MAC地址为00．15．C5．C1．5E．28，IP地址为10．2．128．100(私有地址)。题47-a图是网络拓扑，题47-b图是该主机进行Web请求的1个以太网数据帧前80B的十六进制及ASCII码内容。请参考图中的数据回答以下问题。

与痰饮形成关系不密切的脏腑是（ ）。

患者反复感染，出血2个月。检查：全血细胞减少，肝、脾、淋巴结肿大，骨髓象及淋巴结活检均发现异常组织细胞及多核巨组织细胞。其诊断是

根据国家赔偿法，单独提出赔偿请求的情况主要有哪些?( )

下列关于法律制定的说法，不正确的为哪一个选项?()

刘某缺席会计人员继续教育培训的行为违背了提高技能的会计人员职业道德规范。提高技能是指会计人员通过学习、培训等手段提高职业技能已达到足够的专业胜任能力的活动。

增值税采用间接的计算方法，以商品货物的( )为计税依据。

音乐童话《龟兔赛跑》创作于20世纪60年代，它采用管弦乐的形式，加上简练的解说表现童话故事，深受孩子们的喜爱，其作者是史真荣。()

Theevolutioninpublicpolicyconcerningthemanufacture,saleandpossessionofsemiautomaticassaultweaponslikeAK-47s,AR-

YouwillhearaninterviewaboutGalapagosAdventureTourinEcuador.Asyoulisten,youmustanswerQuestions21to30bywriti

与痰饮形成关系不密切的脏腑是（　　）。

根据国家赔偿法，单独提出赔偿请求的情况主要有哪些?(　　　)

增值税采用间接的计算方法，以商品货物的(　　)为计税依据。