首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于等于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了 (61)
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于等于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了 (61)
admin
2016-05-10
42
问题
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于等于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了 (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
软件设计师上午基础知识考试
软考中级
相关试题推荐
动态主机配置协议DHCP具有(158)机制,这是与BOOTP的主要区别。DHCP协议支持的中继代理(Relay Asent)是一种(159),可以在不同的网段之间传送报文。在DHCP的地址分配方案,(160)是最适合移动终端的分配方案。使用Windows2
动态主机配置协议DHCP具有(158)机制,这是与BOOTP的主要区别。DHCP协议支持的中继代理(Relay Asent)是一种(159),可以在不同的网段之间传送报文。在DHCP的地址分配方案,(160)是最适合移动终端的分配方案。使用Windows2
ADSL(非对称数字用户线)是采用(143)调制的接入技术,其下行速率为1Mb/s~(144),上行速率为640Kb/s~1Mb/s。ADSL接入互联网的两种方式是:(145)。Cable Modem又叫线缆调制解调器,它可以连接用户家中的PC机和(146
CCITT和EIA RS-232都是物理层的电气特性标准,其中CCITT的V.11建议中规定(138)。常用的EIA RS-232接口的电气特性与CCITT的(139)兼容,并且,在这种电路中,数据“1”的接口电平规定为(140)。在RS-232定义的接口
下面关于二级目录的叙述中,错误的是(1)。多级目录结构的特点是(2)。文件系统实现按名存取主要用来实现(3)。文件系统采用二级文件目录可以(4)。为了解决不同用户文件的“命名冲突”问题,通常在文件系统中采用(5)。
页式虚拟存储系统的逻辑地址是由页号和页内地址两部分组成,地址变换过程如图2—8所示。假定页面的大小为8KB,图中所示的十进制逻辑地址9612经过地址变换后,形成的物理地址a应为十进制()。
某企业经过多年的发展,在产品研发、集成电路设计等方面取得了丰硕成果,积累了大量知识财富,()不属于该企业的知识产权范畴。
知识产权一般都具有法定的保护期限,一旦保护期限届满,权利将自行终止,成为社会公众可以自由使用的知识。(20)权受法律保护的期限是不确定的,一旦为公众所知悉,即成为公众可以自由使用的知识。
若需要对一个对象结构中的对象进行很多不同的并且不相关的操作,而你想避免让这些操作“污染”这些对象的类,那么应选择哪种设计模式?(30)。
Inaworldwhereitseemswealreadyhavetoomuchtodo,andtoomanythingstothinkabout,itseemsthelastthingweneediss
随机试题
滑动轴承的摩擦状态大多数情况下处于()。
都是联绵词的一组是()
A.alotofmoneyB.expresspublicfeelingonlocalissuesC.morningD.localpeopleE.nationalissuesF.localissuesMany
冠状动脉CTA在临床应用广泛,关于冠状动脉CTA。冠状动脉CTA的适应证错误的是
商业银行贷给同一借款人的贷款金额不得超过银行资本金额的( )。
基金托管人应当履行的职责包括()等。
在收容教养期间,对被收容教养的未成年人实行( )方针。
根据所给材料,回答下面问题
建设生态文明,必须保护生态环境。保护生态环境的根本之策是
Inthepastdecade,newscientificdevelopmentsincommunicationshavechangedthewaymanypeoplegatherinformationaboutpoli
最新回复
(
0
)