首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于等于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了 (61)
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于等于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了 (61)
admin
2016-05-10
22
问题
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于等于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了 (61) 算法设计策略。已知确定基准元素操作的时间复杂度为Θ(n),则快速排序算法的最好和最坏情况下的时间复杂度为 (62) 。
(62)
选项
A、Θ(n)和Θ(nlgn)
B、Θ(n)和Θ(n
2
)
C、Θ(nlgn)和Θ(nlgn)
D、Θ(nlgn)和Θ(n
2
)
答案
D
解析
本题考查快速排序算法。快速排序算法是应用最为广泛的排序算法之一。其基本思想是将n个元素划分为两个部分:一部分元素值小于某个数;另一部分元素值大于某个数,该数的位置确定;然后进一步划分前面部分和后面部分。根据该叙述,可以知道,这里采用的是分治算法设计策略。
由于已知划分操作的时间复杂度为Θ(n),不需要合并子问题的答案。对于最好的情况,应该是每次划分都把n个元素划分为大约2个n/2个元素的子数组,此时T(n)=2T(n/2)+Θ(n)
解该递归式,可得时间复杂度为Θ(nlgn)。若刚好划分的极度不均衡,即每个划分刚好把n个元素划分为一边0个元素,一边n—1个元素,此时
T(n)=T(n一1)+Θ(n)
解该递归式,可得时间复杂度为Θ(n
2
)。
转载请注明原文地址:https://kaotiyun.com/show/KkRZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
基于TCP/IP的互联网服务中,IP协议提供主机之间的(31)分组传输服务。TCP协议提供端口之间的(32)报文传输服务 UDP属于(33)协议,从其下一层接收了数据以后,根据(34)将之分解成UDP数据报;应用层的(35)协议可以使用UDP或TCP协议传
对于UML提供的一系列支持面向对象的分析与设计的图,(48)给出系统的静态设计视图;(49)对系统的行为进行组织和建模是非常重要的;(50)和(51)都是描述系统动态视图的交互图,其中(52)描述了以时间顺序组织的对象之间的交互活动,(53)强调收发消息的
客户/服务器模式产生于20世纪(27)上年代,它是基于(28)的要求而发展起来的。客户/服务器模式的第一个软件产品是(29)系统,客户/服务器模式通常在(30)环境下运行,客户端的软件具有(31)。
计算机执行程序所需的时间P可用P=I*CPI*T来估计,其中I是程序经编译后的机器指令数,CPI是执行每条指令所需的平均机器周期数,T为每个机器周期的时间。RISC计算机采用(13)来提高机器的速度,它的指令系统具有(14)的特点。指令控制部件的构建,(1
下面关于著作权的描述,不正确的是()。
系统测试是将软件系统与硬件、外设和网络等其他因素结合起来,进行信息系统的各种组装测试和确认测试,(55)不是系统测试的内容。
以下关于进程的描述,错误的是(1)。
Object-oriented analysis(OOA)is a semiformal specification technique for the object-oriented paradigm. Object-oriented analysis
XML is a(71)language for documents containing(72)information. Structured information contains both content(words, pictures, e
随机试题
以下晕针处理方法有错误的是
A、可致过敏性休克B、可致牙齿黄染C、对结核杆菌、麻风杆菌可发挥杀菌作用D、对听觉功能有损害E、抑制骨髓造血功能青霉素
亚甲蓝试验瘘孔流出清亮液的病人,静脉推注靛胭脂5ml,10分钟见到瘘孔流出蓝色尿液,可确诊为()。
关于国际投资法相关条约,下列哪些表述是正确的?(2013年卷一80题)
下列关于固体燃料(煤)的性质说法错误的是()。
根据案例背景,回答以下问题。某市三建公司承揽的某高校学生宿舍工程,由于工程师的缘故造成工程损失,按照FIFIC合同条件和我国《建设工程施工合同示范文本》规定:承包人提交一份最终索赔报告须是在干扰事件影响结束后的()天内。
商业银行开展个人理财业务应遵守的基本原则是()。
识别经纬线是我们认识地球的最基本方法。若图中b、c、d、e表示气压中心,当b处气压势力强盛时,则下列说法正确的是()。
班杜拉提出自我效能感就是
下面叙述中错误的是()。
最新回复
(
0
)