首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2023-02-06
58
问题
基于比较方法的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/XIwD777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
班级授课制是指学生按年龄和文化程度分成固定人数的班级，教师根据课程计划和规定时间表进行教学的一种组织形式。下列不属于班级教学的优点的是()。
在班级开展的各种活动中，每一个成员都会通过自己和他人的表现以及所获得的评价，判断其表现的优势与不足。这主要体现了班级的()。
50．将符号所代表的新知识与学习者认知结构中已有的适当观念建立起非人为的、实质性的联系属于()。
美国单轨学制自下而上的结构是小学、中学，而后可以升人大学，其特点是一个系列、多种分段，即“六三三”“五三四”等。自美国单轨学制设立以来，世界上许多国家纷纷效仿，其主要原因是单轨学制有助于()。
A、B两个乡镇分布于山谷两侧，山谷间有一条宽为2km的河道(如下图所示)。当地政府决定在两个乡镇间修建一条跨河公路促进旅游发展。由于架桥费用高昂，所以要求跨河公路中的桥梁路段长度最短。那么根据图中数据，从A镇前往B镇的最短距离为()。
2020年末，全国共有艺术表演团体17581个，从业人员43．69万人，其中各级文化和旅游部门所属艺术表演团体2060个，从业人员10．75万人。2020年，全国文化和旅游部门所属艺术表演团体共组织政府采购公益演出13．38万场，比上年下降14．9％；观众
除了探矿队员，很多矿石收藏家也对铀矿石感兴趣，因为它们实在太漂亮了。然而学过物理、化学的人都知道，不管化学上结合成什么物质，铀元素的放射性都是不会变的，那么把含铀的“毒花”放在博物馆甚至家里，真的没事吗?实际上，只要隔着一层玻璃，这些铀矿石就算放在卧室里都
与其他生命形式一样，适宜、稳定的自然环境，是人类文明得以存在和延续的重要外部条件。纵观地球生命的进化史，仅仅由于温度、水汽循环或者氧气含量的变化超出了当时地球生命的承受范围，就造成了四次生物大灭绝事件。我们人类的形成历史仅有500万年，在此期间，虽然没有发
若G是一个具有36条边的非连通无向图(不含自回路和多重边)，则图G的结点数至少是()。
在线索二叉树中，结点*p没有左子树的充要条件是()。
随机试题
构成比重要特点是各组成部分的百分比总和为
患者，女，38岁。洗衣时突发右侧肢体活动不利。查体：意识清，失语，听诊二尖瓣听诊区可闻及双期杂音，心律绝对不齐，右侧偏瘫，上肢重于下肢，右侧偏身感觉减退。最可能的诊断是
A．龙胆泻肝汤B．菟丝子散C．缩泉丸D．八正散E．补中益气汤合缩泉丸
促进疾病向恶化或死亡等不良结局转化是由于
城市土地的经济评价是根据城市土地的()两方面属性做出的。
在软土、沼泽地区，地基湿软，地下水位较高的情况下，用()处理会收到较好的效果。
本月允许抵扣的增值税进项税额为( )元。本月销项税额为( )元。
WindowsXP提供了一个基于图形的多任务、多窗口的环境。()
简述生产物流计划的任务
【B1】【B10】
最新回复
(
0
)
