首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2023-02-06
34
问题
基于比较方法的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
学硕统考专业
相关试题推荐
下列选项中，影响教育功能发挥的最直接因素是()。
劳动者和用工企业发生劳动争议后，双方可选择协商、调节、仲裁、诉讼集中争议解决方式。若劳动者选择诉讼，则可直接以诉讼形式解决劳动争议。()
人体是一个庞大的共生体。人体皮肤表面、口腔、呼吸道、肠道________着大量微生物，它们的数量是人体本身细胞的数十倍，编码的基因是人体基因的100倍。每个人的身体里都会有微生物留存的痕迹，而人体的健康会与体内的菌群________。人们将特定环境中包括微
2016—2020年我国住房公积金实缴职工人数年增长超过4％的年份个数是：
请从所给的四个选项中，选出最恰当的一项填入问号处，使之呈现一定的规律性。
2020年末，全国共有艺术表演团体17581个，从业人员43．69万人，其中各级文化和旅游部门所属艺术表演团体2060个，从业人员10．75万人。2020年，全国文化和旅游部门所属艺术表演团体共组织政府采购公益演出13．38万场，比上年下降14．9％；观众
创新是指以现在的思维模式提出有别于常规或常人思路的见解为导向，利用现有的知识和物质，在特定的环境中，本着理想化需要或为满足社会需求。而改进或创造新的事物(包括产品、方法、元素、路径、环境)，并能获得一定有益效果的行为。根据上述定义，下列不属于创新的是：
某部门举行年会抽奖活动。抽奖箱里有80个抽奖券，共20个不同的数字，每个数字均出现4次，且分别对应一份礼品，不同的数字对应的礼品不同。每人当天限抽1次。那么最少多少人当天参加抽奖活动，才能保证至少有3人领取的礼品相同?
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2h-1]中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild，data，rchild)，根结点所在链结点的指针由T给出。
在线索二叉树中，结点*p没有左子树的充要条件是()。
随机试题
根据公务员考核的有关规定，连续()年年度考核被评为“不称职”等级的公务员将被辞退。
可用于镇静催眠的药物是
辅助生产车间的制造费用可以直接计入“辅助生产费用”科目核算的条件有【】
工程质量事故处理的方案类型有( )。
甲、乙两人因遗产继承发生纠纷后，签订仲裁协议向某仲裁委员会仲裁。后乙反悔向遗产所在地法院提起诉讼。法院受理后，甲声明两人有仲裁协议，法院处理的方式是()。
下图是连续分裂的细胞在各个不同时期DNA含量的测定结果，请根据此图回答：研究染色体的形态和数目最好在_______。
下列材料是某老师的一节思想品德课的课堂实录片段：课题：肖像和姓名中的权利教学实录：教学过程：(一)活动一：走进情景——落实姓名的含义及作用呈现材料：有一对夫妇，生了个胖儿子，夫妻俩开心之余，忙着为
同盟会纲领：“驱逐鞑虏，恢复中华，创立民国，平均地权”，这里“鞑虏”指的是()。
甲、乙二人在400米的环形跑道上练习跑步，甲出发1分钟后乙同向出发，乙出发3分钟后第一次追上甲，又过了10分钟，乙第二次追上甲。此时，乙比甲多跑了300米，则甲、乙的出发点在跑道上相距多远?
将两个长度为n的递增有序表归并成一个长度为2n的递增有序表，最少需要关键字间的(30)次比较。
最新回复
(
0
)
