首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知待排序的n个元素可分为n/k个组,每个组包含k个元素,且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为( )。
已知待排序的n个元素可分为n/k个组,每个组包含k个元素,且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为( )。
admin
2019-01-30
34
问题
已知待排序的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
学硕统考专业
相关试题推荐
“二战”后,美国以经济手段扶植和控制西欧的表现是()。
选项中属于古埃及早王朝第一王朝的文物是()。
下列选项中对袁世凯死后的新旧约法之争,描述不正确的是()。
下列明末清初来华传教士,按时间顺序排列,正确的是()。
1852年,英国驻广州代办密切尔说:“经过和这么一个大国开放贸易十年之久,并且双方都已废除了一切独占制度,而拥有如此庞大人口的中国,其消费我们的制品竟不及荷兰的一半……这好像是一个奇怪的结局。”这是因为()。
“瓜步之战”发生在下列哪两个政权之间?()
系统阐明社会主义初级阶段理论是在()。
支持多道程序的操作系统,区别于其他操作系统的主要特征为()。
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址?(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构连入网络并使用所分配的地址对TC
假设二叉树采用二叉链表存储结构存储,试设计一个算法,求出该二叉树中第一条最长的路径长度以及此路径上各结点的值。
随机试题
下列汉字中,属于形声字的是()。
艺术创作的四个心理要素是【】
由于喜欢某人、某群体或某件事,乐于与其保持一致或采取与其相同的表现,这是态度形成过程中的哪一个阶段?()
下列有关温度与显影性能的说法,错误的是
银行汇票丧失,可以由失票人通知付款人或者代理付款人挂失止付。()
“我们要办一种适合儿童的教育,而不是挑选适合教育的儿童”,这反映了素质教育是一种()的教育。
“有志者、事竟成,破釜沉舟,百二秦关终属楚;苦心人、天不负,卧薪尝胆,三千越甲可吞吴。”此联所涉及的历史事件分别发生在()。
“五十六个星座,五十六枝花,五十六族兄弟姐妹是一家”,这首歌家喻户晓,广为传唱,歌颂了我国平等、团结、互助的社会主义新型民族关系。民族区域自治是我国确保新型民族关系的基本政治制度。在这种制度下,各自治机关()①是自治地方的权力机关
下列关于中国古代契约的规定,正确的有()。
北洋政府制定的刑法典是()。
最新回复
(
0
)