首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知待排序的n个元素可分为n/k个组,每个组包含k个元素,且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为( )。
已知待排序的n个元素可分为n/k个组,每个组包含k个元素,且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为( )。
admin
2019-01-30
36
问题
已知待排序的n个元素可分为n/k个组,每个组包含k个元素,且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为( )。
选项
A、O(nlog
2
n)
B、O(nlog
2
n)
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/7KRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
中古时代实行索贡巡行赋税征收方式的国家是()。
以下关于国际联盟与联合国的表述,正确的是()。
汉灵帝熹平四年(175),学者用隶书写成五经,镌刻成碑,立于太学,这就是《熹平石经》,这是我国最早的官方定本的经书,以下参与此次校对的学者有()。
下列选项中不属于《国际联盟盟约》内容的是()。
太平天国作为几千年来农民运动的高峰,所遇到的历次农民运动中不曾有过的新情况是(
到1869年为止,人类已发现了多少种化学元素()。
汉章帝会群儒于白虎观,讨论经义,由()写成《白虎通德论》(又称《白虎通义》、《白虎通》)一书,这部书系统地吸收了阴阳五行和谶纬之学,形成今文经学派的主要观点。
已知散列函数为H(key)=key%11,处理冲突的方法为二次探测法,探测的序列为:1,-1,4,-4,…,j2,-j2(j<=m/2)。当di>0时,Hi=(H(key)+di)%m当di<0时,Hi=(H(key)+di+m)%m散列
设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1则T中的叶子数是()。
m阶B一树是一棵()。
随机试题
钢与铜及铜合金焊接时,产生焊缝裂纹、渗透裂纹的原因有哪些?
下列各句,没有语病的一句是()
A.阴阳的相互制约关系B.阴阳的互根互用关系C.阴阳的消长平衡关系D.阴阳的相互转化关系“阴损及阳。阳损及阴”的理论依据是
提出血府逐瘀汤治疗瘀血发热的医家是:
我国的《民用建筑热工设计规范》(GB50176—1993)将我国分成了5个气候区,分区的主要依据是:[2004年第36题]
各备用电源放电终止,再充电()h后断开设备主电源,备用电源至少应保证设备工作8h,且应满足相应的标准及设计要求。
我国体育的目的是:增强人民体质,促进入的全面发展,丰富()生活,为社会主义建设服务。
根据下面文字资料,回答116~120题。世界煤储量在世界能源总储量中占90%,按目前规模开采可持续200年左右。据19世纪80年代初世界能源会议等组织的资料,世界煤资源地质储量为14.3万亿吨,其中探明储量为3.5万亿吨,约占24.5%;在总储量中
A、 B、 C、 D、 A本题的规律为,每个图形由相交的两条射线组成,竖直方向的射线保持不动,水平方向的射线以交点为轴,按照逆时针方向依次旋转135°。旋转至第三个图形,两条射线呈180°夹角(并非重合),因
Itiseasytodeterminewhethersmokingishazardous.Smokingreducesone’slifeexpectancy.
最新回复
(
0
)