首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2023-02-06
31
问题
基于比较方法的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://jikaoti.com/ti/KkPiFFFM
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
在学习立体几何的时候，有些学生能够非常迅速地接受并绘制出三维立体图形，而有些学生则要经过很长时间的学习才能慢慢接受。这体现了学生在()方面的差异。
以下选项中体现“学生学习方式转变”的新课程观点是()。
材料一新春伊始，《新农村》记者小梁到基层调研，以下是他在两个村庄采访的片段。“村子真于净”，这是外来人对东各村的第一印象。村道上见不到一张纸片，家家院里院外也清清爽爽。79岁的高大妈笑着把小梁往屋里迎。冬季取暖煤改电以后，高大妈家装了地暖，外面再
给定资料： 1．阆中的乡村学校大都依山而建，地形狭长而起伏。在经过若干年的撤点并校之后，形成了以九年一贯制的中心学校为主体的格局。校园都有相似之处，但又会让来访者耳目一新，其中有许多教育局要求的“标配"，比如用学生们的彩色大头照拼成的“笑脸墙"，师生共同
给定资料： 1．阆中的乡村学校大都依山而建，地形狭长而起伏。在经过若干年的撤点并校之后，形成了以九年一贯制的中心学校为主体的格局。校园都有相似之处，但又会让来访者耳目一新，其中有许多教育局要求的“标配"，比如用学生们的彩色大头照拼成的“笑脸墙"，师生共同
虽然树种对水分的利用规律大同小异，但不同的森林类型涵养水源的作用大小不一。科学评估显示，长江上游天然林保护工程的实施为岷江上游的水生态安全做出了明显贡献，但大面积的人工植被覆盖可能加重区域生态用水，从而降低流域产水量，且大规模集中连片种植的人工纯林引发的外
微躺青年：指面对现实中的竞争压力，既不参与过度竞争，也不消极接受现状，而在专注于本职工作的同时，合理调整工作方向，追求自我价值实现的年轻人。下列属于微躺青年的是：
如下图所示，装有水的烧杯放在天平一端，另一端放置砝码使天平平衡，此时再放入一手指在水中，若手指完全静止在水中且没有触碰烧杯壁和烧杯底部，且水也没有溢出，那么这时天平的状态是：
A、B两个乡镇分布于山谷两侧，山谷间有一条宽为2km的河道(如下图所示)。当地政府决定在两个乡镇间修建一条跨河公路促进旅游发展。由于架桥费用高昂，所以要求跨河公路中的桥梁路段长度最短。那么根据图中数据，从A镇前往B镇的最短距离为：
随机试题
下列句子分别编为四组，全都表现苏武的爱国气节的一组是()。①汉武帝嘉其义②引佩刀自刺③举剑欲击之④武卧啮雪与旃毛并咽之⑤律知武终不可胁⑥常愿肝脑涂地
在微型计算机的汉字系统中，一个汉字的内码占__________个字节。
不宜采用塑化疗法的是
与青霉素联用，治疗细菌性肺炎，有协同增效作用的是()。
甲、乙类厂房严禁采用()。
下列不属于信息技术风险控制内容的是( )。
买断式回购采用()的方式。
关于质量发展的三个阶段，下列说法正确的有()。
给定资料1．近年来，陕西省西安市本土自媒体兴起，吸引了大家的目光。从小生活在西安的王江很快有了自己的想法：“我想创办自己的公众号，把我眼中的西安宣传展示给大家。”“相遇西安”成立于2017年年底，创始人王江带领小团队，不断摸索与尝试，最终在西安的
A、Shehasboughtanewone.B、Herbrotherhasjustgivenherone.C、Shehasonlyanoldone,D、Shehasnoneatpresent.D男士说“我想能
最新回复
(
0
)
