首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于等于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了 (61)
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于等于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了 (61)
admin
2016-05-10
43
问题
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于等于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了 (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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在FDM中,主要通过(31)技术使各路信号的带宽(32)。使用FDM的所有用户(33)。从性质上说,FDM比较适合于传输(34),FDM的典型应用是(35)。
分组交换可以采用虚电路方式或(26)方式实现。虚电路方式在通信前需建立一条虚电路,其路径由(27)决定。每条虚电路都有虚电路号码,该号码(28)。虚电路建立后,各数据分组(29)到达目的地,然后(30)。
CCITT和EIA RS-232都是物理层的电气特性标准,其中CCITT的V.11建议中规定(138)。常用的EIA RS-232接口的电气特性与CCITT的(139)兼容,并且,在这种电路中,数据“1”的接口电平规定为(140)。在RS-232定义的接口
基于TCP/IP的互联网服务中,IP协议提供主机之间的(6)分组传输服务 TCP协议提供端口之间的(7)报文传输服务:UDP属于(8)协议,从其下一层接收了数据以后,根据(9)将之分解成UDP数据报;应用层的(10)协议可以使用,UDP或TCP协议传输数据
透明网桥可以决定网络中的路由,而网络中的各个站点均不负责路由选择。网桥具有帧过滤功能,网桥从其某一端口收到正确的数据帧后,在其地址转发表中查找该帧要到达的目的站,若查找不到,则会(243);若要到达的目的站仍然在该端口上,则会(244)。图3.1为两个局域
因争用资源产生死锁的必要条件是互斥、循环等待、不可抢占和()。
如果希望别的计算机不能通过ping命令测试服务器的连通情况,可以(1)。如果希望通过默认的Telnet端口连接服务器,则下面对防火墙配置正确的是(2)。(2008年上半年试题)(2)
Certificates are(16)documents attesting to the(17)of a public key to an individual or other entity. They allow verification of t
软件需求说明书是需求分析阶段的最后成果,(17)不是其应包含的内容。
赵某于2002年4月1日申请一项外观设计专利,2003年2月8日获得授权,这项专利权的保护期限终止于______。
随机试题
是我们自己的所为和所不为决定着我们的未来。
下列关于祛痰药的叙述中,不正确的是
患儿,3岁。不思进食,泛恶,夜间哭闹少寐,腹胀,舌苔厚腻垢浊。其诊断是
A,D-洋地黄毒糖B,D-洋地黄糖C,D-加拿大糖D,L-鼠李糖E,葡萄糖属于6-去氧糖的是
产妇王某,34岁,宫内孕39+3周。于入院前一天晚出现宫缩,清晨起来又消失。入院当天中午,孕妇又开始出现宫缩,每4—5分钟一次,每次持续约30秒。为了早接触、早开奶,提倡将新生儿放在母亲胸前进行吸吮是在出生后
典型的响应级别通常可分为()。
持续经营假设是假设企业可以长生不老,即使进入破产清算,也不应该改变会计核算方法。()
某幼儿给一堆玩具分类,第一次按大小分类,第二次按颜色分类,第三次按材料分类。该幼儿的分类是按()
已知矩阵(I)求可逆矩阵P,使(AP)T(AP)为对角矩阵;(Ⅱ)若A+kE正定,求k的取值.
Wehadamarvelousholiday.Onlythelasttwodayswereslightly________byweather.
最新回复
(
0
)