首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知待排序的n个元素可分为n／k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。
已知待排序的n个元素可分为n／k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。
admin
2017-11-14
62
问题
已知待排序的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/k3Ri777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
中国共产党在过渡时期总路线的主要内容是“一化三改造”，其中“一化”是指()。
第二次世界大战后，国际关系最大的变化是()。
宁夏回族自治区的设立时间是()。
戈尔巴乔夫上台后，在和平共处五项原则基础上，推动苏中关系正常化，这一做法主要表明了()。
改革开放以后，我国农村产业结构巨大的转变表现在()。
阅读材料，回答以下问题：一、大清帝国之皇统，万世不易。二、皇帝神圣，不可侵犯。三、皇帝权以宪法规定为限。四、皇帝继承之顺序，于宪法规定之。五、宪法由资政院起草议决，皇帝颁布之。六、宪政改正提案权，属于国会。七、上院议员，由国民于法定特别资格公选之。八、总
阅读材料，回答以下问题：重庆中央党部，暨中央执监委员诸同志均鉴：今年4月，临时全国代表大会宣言，说明此次抗战之原因，曰：“自塘沽协定以来，吾人所以忍辱负重与倭国周旋，无非欲停止军事行动，采用和平方法，先谋北方各省之保全，再进而谋东北四省问题之合理解决，
西汉初年，反驳刘邦“马上治天下”的说法，并向汉帝国治国献策的是()。
编写判定给定的二叉树是否是二叉排序树的函数。
设一段正文由字符集{A，B，C，D，E，F)中的字母组成，这6个字母在正文中出现的次数分别为{12，18，26，6，4，34)。(1)为这6个编码设计哈夫曼编码。(2)设每个字节由8位二进制位组成，试计算按哈夫曼编码压缩存储这段正文共需多少个字
随机试题
患者，男，50岁，平常嗜烟酒，有胆囊结石病史，昨晚饮酒和暴食后，出现左上腹疼痛，最可能的疾病是
一个Excel工作簿最多可设置工作表的个数是
下列关于第二审程序的说法中错误的是：()
()是服务提供方与客户充分沟通后，向客户提供的实施服务的工作设想，经客户批准，作为约定服务提供方实施服务管理的细则。
报关企业接受进出口货物收发货人的委托，以委托人的名义办理报关手续的，应当向海关提交由委托人签署的授权委托书。()
跨栏跑时，摆动腿跨过栏后积极下压，()落地。
请认真阅读下文，并按要求作答。王鹏每周计划跑5．6千米，他每天要跑多少千米?5．6÷7=______(千米)王鹏的爷爷每天坚持慢跑1．8千米，需要12分钟。爷爷慢跑的速度是多少?1．8÷12=______(千米)做一做：(1)7．83÷9
下列事项中，不可以进行行政复议调解的是()。
将“受信任的站点”的安全级别设置为“高”。
设有一个用线性探测法解决冲突得到的散列表：散列函数为H(k)=kmod11若查找元素15，则探测的次数(比较的次数)为（）。
最新回复
(
0
)
