首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2017-11-14
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://kaotiyun.com/show/C3Ri777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
1901年6月,发表《立宪法议》,首先提出君主立宪要求的是()。
洋务派创办军事工业的方式是()。
巴黎和会召开的时间是()。
全国高校院系调整的具体时间是()。
下列对1918年德国十一月革命说法不正确的是()。
西汉初年,反驳刘邦“马上治天下”的说法,并向汉帝国治国献策的是()。
宋代至清代我国书籍印刷的主要方式是()
《中国人民解放军宣言》发表的具体时间是()。
下列排序算法中,时间复杂度为O(nlogn)且占用额外空间最少的是()。
已知一个线性表为(38,25,74,63,52,48),假定采用H(K)=Kmod7计算散列地址进行散列存储,若利用线性探测的开放定址法处理冲突,则在该散列表上进行查找的平均查找长度为();若利用链地址法处理冲突,则在该散列上进行查找的平均查找长度
随机试题
你们单位的局长经常越过科长给你下达任务,对此科长很不高兴,请问你要怎么处理这样的情况?
金属管道腐蚀按照腐蚀环境分为海水腐蚀、()、大气腐蚀和土壤腐蚀。
A.前列腺B.尿道球腺C.精囊D.前庭大腺E.尿道球有后尿道穿行其中的是()
心脏右前斜位吞服钡餐的目的是为了观察
A.头B.足C.手D.背E.胸腹手三阳经与足三阳经相交于
当单位利益与社会公众利益发生冲突时,会计人员应该首先维护社会公众利益。()
企业的下列财务活动中,不符合债权人目标的是()。
甲公司是一个已经成立并运行了5年的企业,其有关情况如下:所在行业的注册资金要求很低,A公司很好地控制了所有地区的销售渠道,生产的产品所需原料A由于具有独特性,只能从供应商乙公司采购,甲公司从乙公司购入原料A占乙公司原料A销售量的90%,甲公司产品B具有独特
单位、个人和银行在票据上签章时,必须按照规定进行。下列签章有效的有()
A、Whethertheyshouldtakethechildhome.B、WhatDr.Myer’sinstructionsexactlywere.C、Whoshouldtakecareofthechildath
最新回复
(
0
)