首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知待排序的n个元素可分为n/k个组,每个组包含k个元素,且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为( )。
已知待排序的n个元素可分为n/k个组,每个组包含k个元素,且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为( )。
admin
2018-08-12
16
问题
已知待排序的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://jikaoti.com/ti/ywfjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
文艺复兴运动兴起的时间是()。
在巴黎和会上获利最大的两个国家是()。
戈尔巴乔夫上台后,在和平共处五项原则基础上,推动苏中关系正常化,这一做法主要表明了()。
第一个五年计划的具体时间段是()。
鉴于汉匈关系的状况,汉初向汉高祖提出和亲政策的是()。
某系统中n个相互独立的生产者进程为一个消费者进程提供数据,假设每个生产者提供的数据写入各不相同的缓冲区,且生产者写缓冲区的速度比消费者读缓冲区的速度快,则缓冲区个数的最优值应为()。
高度为7的AVL树最少有()个结点。
随机试题
大坝受水流冲击力最大的部位是()。
兵种领导机关包括哪些。
缺铁性贫血铁剂治疗有效,最早的变化指标是
A.性别、药味名称B.剂数、用法C.药物名称、姓名D.医师签字E.用法、医院名称属处方后记的内容是
去除口臭宜选用的漱口液是
未满十七岁的张某应聘于某施工单位,下列关于此事说法正确的是()。
课堂导入的作用主要体现在集中注意、引发兴趣、进入课题。()
阅读以下文字,完成下列问题。《进一步做好新形势下就业创业工作重点任务分工方案》(以下简称《分工方案》)已经国务院同意,请各省、自治区、直辖市人民政府以及国务院有关部门认真落实。有关部门要认真贯彻实施甲,按照《分工方案》的要求,进一步分解
设f’(x)=arcsin(x-1)2,f(0)=0,求∫01f(x)dx.
It’simpossibletopredictwhethershe’llbewellenoughtocomehomefromhospitalnextmonth.
最新回复
(
0
)