首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2017-01-04
82
问题
基于比较方法的n个数据的内部排序,最坏情况下的时间复杂度能达到的最好下界是( )。
选项
A、O(nlog
2
n)
B、O(log
2
n)
C、O(n)
D、D(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/mQRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
对《魏玛宪法》的内容和影响叙述不正确的是()。
下列改革内容不是在《天朝天亩制度》中提出的一项是()
简述近代香港问题的形成。
试述明治维新过程中土地改革的主要内容和意义。
简述士族的源流和在西晋的发展过程。
诸侯国的国君如何用人呢?有人主张:“左右皆曰不可,勿听;诸大夫皆曰不可,勿听;国人皆曰不可,然后察之,见不可焉,然后去之。”这种主张最终可能出自下列哪位思想家之口()。
1962年1、2月间,中共中央召开的统一思想、总结经验教训、明确工作方向的会议是()。
最早以立法形式巩固大化改新成果的法令是()。
对斯大林时期形成的高度集中的社会主义经济政治体制的叙述,不确切的是()。
一个客户机利用FTP协议从服务器上下载文件,如下图所示为整个过程中协议交换的过程,请回答如下问题:(1)该协议层图中第四层协议是什么?(2)如果FTP客户端采用了LIST命令来获得FTP服务器上的文件列表,该列表采用什么端口传输?
随机试题
男性,60岁,突然觉头痛、头晕伴恶心、呕吐,测血压为240/140mmHg,该病例的急救措施为
治疗心室率为68次/分的Ⅱ度I型房室传导阻滞,应
男性,65岁,胃溃疡病史20年,常于餐后出现中上腹疼痛,服氢氧化铝可缓解,近一年来疼痛不似从前有规律,且服氢氧化铝也难以缓解,伴消瘦,来诊。查:大便隐血阳性,最可能的诊断是
甲村村委会以营利为目的,擅自将属于该村民集体所有的一块土地租给乙公司用于建造乡村别墅,被县土地行政主管部门发现,该部门依法可采取的措施包括下列哪些?()
下列拟作出的决定中,行政机关应告知当事人有权要求听证的是()。
道路纵坡最好在()之间。
下列关于两类错误的描述正确的有()。
B市的张女士在H区将私家车停在马路边,到饭店吃饭,饭后发现车上有一张“停车记录告知单”。张女士不明白这张“告知单”是什么,通过网络查阅,得到如下信息:B市从2011年4月1日起,交通协管员发现机动车未在道路停车泊位内停放的,按规定须填写两份单子:一份是《B
尽管借款人愿意支付合同利率甚至更高的利率,贷款人可能也会拒绝提供贷款,这种现象被称为()。(对外经济贸易大学2013真题)
认识要实现从感性认识向理性认识飞跃,需要具备的基本条件有()
最新回复
(
0
)