首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于等于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了 (61)
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于等于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了 (61)
admin
2016-05-10
25
问题
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于等于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了 (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://jikaoti.com/ti/Mdf7FFFM
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
X.25网络是根据(21)的X.25建议书实现的计算机网络。X.25网络的物理层使用的标准是(22),数据链路层使用的标准是(23),第三层传输的数据单位是(24)。X.25网络中的PSE采用(25)的方法交换分组。
在以下数字调制方法中,抗干扰性能最好的是(36)。为提高数据速率,对数据进行调制时可采用的办法是(37)。与PSK相比,QPSK的最大特点是(38)。目前流行的Modem采用(39)进行调制。采用每种相位各有两种幅度的PAM调制在带宽为8kHz的无噪声信道
FDDI中采用(21)编码技术,使编码效率提高到(22),这对于100Mb/s的光纤网,则意味着只需要125MHz元件就可以实现。为了得到足够的同步信息,FDDI实际采用二进制编码方法,即先按(23)编码后,再用(24)。为了消除环网中数据的时钟偏移,FD
基于TCP/IP的互联网服务中,IP协议提供主机之间的(31)分组传输服务。TCP协议提供端口之间的(32)报文传输服务 UDP属于(33)协议,从其下一层接收了数据以后,根据(34)将之分解成UDP数据报;应用层的(35)协议可以使用UDP或TCP协议传
在基于TCP/IP的互联网服务中,传输层的UDP协议提供进程之间(6)报文传输服务,TCP协议提供进程之间(7)报文传送服务。TCP使用三次握手协议建立连接、传输报文,使用修改的三次握手协议来关闭连接。关闭连接时,设甲乙两方发送报文的序号分别为X和Y,甲方
ISO9000系列标准和软件成熟度模型CMM都着眼于质量和过程管理。ISO9000系列标准的主导思想如下:(1)强调质量(4);(2)使影响产品质量的全部因素始终处于(5)状态;(3)要求证实企业具有持续提供符合要求产品的(6):
FDDI与Token Ring的MAC帧格式较为相似,分为上(1)两种,在它们的MAC帧中(2)。在编码方面,FDDI采用的编码方式是(3),编码效率为(4),而Token Ring采用的编码方式是(5),编码效率为(6)。
Linux是使用最为广泛得网络操作系统之一。在linux网络配置文件中有几个较为重要的配置文件:用于存放本机主机名以及经常访问IP地址的主机名的是(34)。Linux下存在两个网络服务守候进程的配置文件。通过修改(35),可以达到关闭或开放某种对应服务的目
若工作站不带磁盘,无法上网登录主机,注意到这种情况,当启动时把硬件地址送到主机,但主机拒绝它们,这是因为__________协议没有工作。
XML is a(71)language for documents containing(72)information. Structured information contains both content(words, pictures, e
随机试题
为了使键槽对称于轴线,必须使键槽铣刀的()通过工件的轴线称为对刀。
最早载录《古诗十九首》的古代典籍是【】
使吸入麻醉药MAC下降的因素有
机械搅拌澄清池是利用转动的叶轮使泥渣在池内循环流动,完成()。
关于综合成本的分析方法,下列说法正确的是()
可以挂失止付的票据包括()。
在传递信息的所有部位中,()可以传递最细微的感情。
根据以下资料。回答下列题。“十一五”期间,我国货物进出口总额累计116806亿美元。其中,出口总额63997亿美元,比“十五”期间增长1.7倍;进口总额52809亿美元,比“十五”期间增长1.4倍。“十一五”前两年,我国货物进出口总额保
在考生文件夹下,打开testdb数据库,完成如下操作:(1)为表sell建立一个主索引,索引名为PK,索引表达式为:部门号+年度+月份。(2)将自由表datatest、model、tabe和pass添加到当前打开的数据库中。
【B1】【B9】
最新回复
(
0
)