首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知待排序的n个元素可分为n／k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。
已知待排序的n个元素可分为n／k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。
admin
2023-02-06
8
问题
已知待排序的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/lIwD777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列关于公文格式页码的说法，正确的有()。
个体将在一种学习中习得的一般原理、方法、策略和态度等迁移到另一种学习中去叫作()。
品德是由道德认识、道德情感、道德意志、道德行为等四个要素构成的综合体。下列关于四者关系的表述，正确的有()。
化学学习中，钾、钠等属于同一抽象和概括层次的金属元素在学习中互相影响。这种学习的迁移叫作()。
给定资料： 1．阆中的乡村学校大都依山而建，地形狭长而起伏。在经过若干年的撤点并校之后，形成了以九年一贯制的中心学校为主体的格局。校园都有相似之处，但又会让来访者耳目一新，其中有许多教育局要求的“标配"，比如用学生们的彩色大头照拼成的“笑脸墙"，师生共同
长期生活不规律会导致免疫细胞和胆同醇积聚在血管壁上，变成粥样斑块。这些斑块破碎时会形成血栓，血栓有可能脱落，沿血管流动。由于牙周病菌是一种厌氧菌，而血管中有大量氧气，因此牙周病菌单独进入血管并不能存活。但是，因为免疫细胞能够有效隔绝血管中的氧气，所以人们认
文化是怎么来的?似乎是一些学者、作家、艺术家、宗教家折腾出来的，其实这一看法过于________。往深层次看，所有文化形态后面都有某种生态的条件和诱因，广义的生态元素——包括地理、气候、物种等——总是参与对文化形成的制约和________。填入画横线部分最
在公众对不同信息源的信任层级排序中，来自政府的消息历来以权威性和________居于前列。同样是传谣，谣言经政府官微传播后破坏力更强，这________。填入画横线部分最恰当的一项是：
微生物是地球最早出现的生命形式。这种简单而古老的生命决定了地球演化的方向和进程，推动了土壤的发生和发育，孕育了人类的文明。事实上，土壤中蕴藏的微生物的多样性，被称为地球关键元素循环过程的引擎，是联系大气圈、水圈、岩石圈及生物圈物质与能量交换的重要纽带，维系
随机试题
黄芩和黄柏都具有的功效是
传染性单核细胞增多症患儿一般不包括下面哪个条件
对疑诊支气管内膜结核的病人，首选进行下列哪项检查
患者，男性，40岁，中上腹部剧烈疼痛、恶心、呕吐、发热10h急诊人院。查：血淀粉酶显著升高，以急性胰腺炎急诊手术，术中空肠造口。术后诊断：急性坏死性胰腺炎。患者恢复口服饮食的初期，需禁用的食物是
吊杆距主龙骨端部距离不得大于()。
关于巨额赎回，下列说法错误的有( )。
企业从银行借入短期借款，不会导致实际利率高于名义利率的利息支付方式是()。
2004年，春城白药开始尝试进军日化行业。而此时日化行业的竞争已经异常激烈。B公司、L公司、D公司、H公司等国际巨头们凭借其规模经济、品牌、技术、渠道和服务等优势，基本占领了C国日化行业的高端市场，占据了C国牙膏市场60％以上的份额；清雅公司、蓝天公司等本
甲股份有限公司（简称甲公司）为主板上市公司，主营业务为生产、销售稀土合金镀层钢丝、钢绞线和PC钢绞线等金属制品，由于甲公司股权比例较为分散，因此不存在实际控制人。2017年2月1日，甲公司公告称因筹划重大资产重组事项，公司股票停盘。甲公司准备与A有限责任公
一次公开观摩课上一位二十多年教龄的女老师，在课堂上并没有频频去叫那些反应机灵、学懂会用的好学生，而是善于捕捉那些不敢大胆发言，没有勇气回答问题的差生的一闪之念。一位女孩刚鼓起勇气抬起头，就被老师叫起来回答，结果由于心理过于紧张，急得满头大汗，不知所措。这时
最新回复
(
0
)
