首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知待排序的n个元素可分为n／k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。
已知待排序的n个元素可分为n／k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。
admin
2018-08-12
17
问题
已知待排序的n个元素可分为n／k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。
选项
A、O(nlog
2
n)
B、O(nlog
2
k)
C、O(klog
2
n)
D、O(klog
2
k)
答案
B
解析
此题考查的知识点是分块排序的思想。因组与组之间已有序，故将n／k个组分别排序即可，基于比较的排序方法每组的时间下界为O(klog
2
k)。可以用二叉树分治形式描述，最好的情况是树的高度为log
2
k。全部时间下界为O(nlog
2
k)。应选B。
转载请注明原文地址:https://kaotiyun.com/show/GuRi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
1994年5月，江泽民在进一步强调正确处理改革、发展、稳定的关系时指出()。
下列现象均属于明朝手工业进步的表现的是()①嘉万年间民营手工业渐居主要地位②匠役制度瓦解③出现了雇佣劳动、组织手工工场的经营方式④加强了对工匠的剥削，工匠的人身依附关系加强
第二次工业革命引起的生产关系方面最突出的变化是()。
巴黎和会上，英美主张把原德国在山东的权利转让给日本，华盛顿会议又表示支持中国让日本归还山东的要求，英美态度发生变化的根本原因是()。
下列城市：①南京②厦门③天津④杭州，按其在近代历史上开放为商埠的时间先后顺序排列应该是()
鉴于汉匈关系的状况，汉初向汉高祖提出和亲政策的是()。
到1869年为止，人类已发现了多少种化学元素()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
三个进程P1、P2、P3互斥使用一个包含N(N＞O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用getev
随机试题
在学生成长和发展过程中起主导作用的是()
《典论·论文》是______的著名艺术批评理论著作。
建筑安装工程含税造价中的税金应包括（）等。
当承重模板的跨度大于4m时，其设计起拱值通常取跨度的()左右。
科学计算是计算机最早应用的领域。()
根据《中华人民共和国进出口关税条例》有关税率运用的规定，下列说法错误的是( )。
2016年1月，甲个人独资企业(下称甲企业)向陈某借款50万元，双方签订了借款合同。合同约定：借款期限为6个月；年利率24％；利息在返还借款时一并支付。合同未约定逾期利率。王某、李某为该笔借款提供了保证担保。在王某、李某与陈某签订的保证合同中，当事人未约定
接收并阅读由luoyingjie@cue．edu．cn发来的邮件，并立即回复，回复内容为“您需要的资料已经寄出，请注意查收！”
Thebirthdayofthe______issometimesservedastheNationalDayofBritain.
GreenhouseEffectI.【T1】_____ofthegreenhouseeffect【T1】______A.About【T2】______ofthesunlightreachesthe【T2】______plan
最新回复
(
0
)
