首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
admin
2019-08-15
37
问题
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
选项
A、O(nlog
2
n)
B、O(log
2
n)
C、O(n)
D、O(n
2
)
答案
A
解析
此题考查的知识点是各类排序的效率。理论上可以证明，对于基于关键字之间比较的分类，无论用什么方法都至少需要进行log
2
(n!)次比较。
由Stirling公式可知，log≈(n!)≈nlog
2
n一1．44n+O(log
2
n)，所以基于关键字比较的分类时间的下界是D(nlog≈n)。因此不存在时间复杂性低于此下界的基于关键字比较的分类。应选A。
转载请注明原文地址:https://kaotiyun.com/show/QdCi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
赋税是我国古代国家宏观管理经济的重要手段。据此回答问题：西汉到北魏赋税制度的变化的基本趋势是()
《中国国民党改组宣言》发表的时间是()。
“两个凡是”
(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，
某计算机有8个主设备需要竞争总线的使用权，其设备号为0～7。现欲设计其判优控制方法，试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制，则在链式查询、计数器定时查询和独立请求三种方式下，
在4×100米接力赛中，4个运动员之间存在如下关系：运动员1跑到终点把接力棒交给运动员2；运动员2一开始处于等待状态，在接到运动员1传来的接力棒后才能往前跑，他跑完100米后交棒给运动员3；运动员3也只有接到运动员2传来的接力棒后才能往前跑，他跑完100米
某计算机采用Cache一主存一磁盘三级存储系统。Cache的访问时间为t1ns，命中率为p1；若Cache未命中，CPU需直接访问主存，访问时间为t2ns，主存命中率为p2；若所需数据字不在主存中，则访问主存未命中、将包含所需数据字的磁盘数据块装入主存共需
给定序列{3，5，7，9，11，13，15，17)，(1)按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求在等概率情况下查找成功的平均查找长度。(2)按表中元素的顺序构造一棵平衡二叉树，并求其在等概率情
设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][O]的存储地址为860，则a[3][5]的存储地址为()。
磁盘机由6个盘片组成，其中专设1个盘面为伺服面，其他的盘面作为记录数据的盘面。盘存储区域内直径为6．1cm，外直径为12．9cm，道密度为220TPM，位密度为6000bpm，平均寻道时间为10ms，磁盘转速为7200RPM。假定7π=3，试计算：
随机试题
合伙企业财产的构成包括合伙人的出资,及以合伙企业名义取得的收益和依法取得的其他财产。()
（）采用各类卷材作为防水层的屋面属于刚性防水屋面。
某体育大厦项目,为节约用水,空调冷却水采用冷却塔冷却循环使用,对洗涤用水,拟安装处理设备,使水经回收处理后二次使用,此举属于()节水措施。
某服装厂厂房为一栋六层钢筋混凝土建筑物，厂房一层是裁床车间，二层是手缝和包装车间及办公室，三至六层是成衣车间。厂房一层原有4个门，后2个门被封死，1个门上锁，仅留1个门供员工上下班进出。厂房内唯一的上下楼梯平台上堆放了杂物仅留0．8m宽的通道供员工通行。半
下列选项中，不属于西画透视法类型的是()。
请对“‘应为而不为’就是刑法上的危害行为”这一说法进行辨析。
毛泽东在《论人民民主专政》一文中指出，人民民主专政的主要基础是()。
微软公司的Project软件属于()。
按照逻辑结构分类，结构可以分为线性结构和非线性结构，栈属于______。
A
最新回复
(
0
)
