首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知待排序的n个元素可分为n/k个组,每个组包含k个元素,且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为( )。
已知待排序的n个元素可分为n/k个组,每个组包含k个元素,且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为( )。
admin
2017-11-14
22
问题
已知待排序的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
学硕统考专业
相关试题推荐
战国初期,上党地区在下列哪一个国家的控制范围之内?()
下面哪部经典是我国最早的官方史书?()
1923年纳粹党魁希特勒发动了“啤酒馆暴动”,对此叙述不正确的一项是()。
晚清时期清帝年号的正确排序是()
乾隆时期,明确规定了驻藏大臣的地位与达赖班禅同等,并实行“金瓶掣签”制度的文件是()。
中古时代实行索贡巡行赋税征收方式的国家是()。
唐朝流传着一句“三十老明经、五十少进士”,这说明了唐代科举()。
第三次科技革命对社会经济结构的影响是()。
材料一材科二(戈尔巴乔夫政府)在制定改革政策方针中存在三个严重问题:第一,仍然以优先发展重工业和机器制造业为主的“加速发展战略”作为发展资本密集型产业的主要战略,已不符合时代潮流。现代经济结构已由资本密集型向技术密集型发展……苏联的经济改革对
宋代至清代我国书籍印刷的主要方式是()
随机试题
副交感神经的主要功能是()。
大拉翅旗头在清代初期就已经普遍流行。()
以下辅料在片剂中作崩解剂的是
引起胰腺细胞坏死的是
简要概述消防车登高操作场地的检查方法的主要操作内容。
2020年1月,甲公司与乙公司签订劳务派遣协议,派遣刘某到乙公司从事临时性工作。2020年5月,临时性工作结束,两公司未再给刘某安排工作,也未再向其支付任何报酬。2020年7月,刘某得知自2020年1月被派遣以来,两公司均未为其缴纳社会保险费,遂提出解除劳
根据《浙江省旅游管理条例》规定,设立旅游度假区,应当报省人民政府和国务院批准。()
设对(Ⅰ)中的任意向量ξ2,ξ3,证明ξ1,ξ2,ξ3线性无关。
Thosewhowishtoscheduletheirannualcheck-upscancallusandmake______inadvance.
Petroleumproducts,suchasgasoline,kerosene,homeheatingoil,residualfueloil,andlubricatingoils,comefromonesource
最新回复
(
0
)