首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下面是快速排序的伪代码,请将空缺处(1)~(3)的内容填写完整。伪代码中的主要变量说明如下。 A:待排序数组 p,r:数组元素下标,从p到r q:划分的位置 x:枢轴元素 i:整型变量,用于描述数组下标。下标小于或等于i的元素
下面是快速排序的伪代码,请将空缺处(1)~(3)的内容填写完整。伪代码中的主要变量说明如下。 A:待排序数组 p,r:数组元素下标,从p到r q:划分的位置 x:枢轴元素 i:整型变量,用于描述数组下标。下标小于或等于i的元素
admin
2010-01-15
67
问题
下面是快速排序的伪代码,请将空缺处(1)~(3)的内容填写完整。伪代码中的主要变量说明如下。
A:待排序数组
p,r:数组元素下标,从p到r
q:划分的位置
x:枢轴元素
i:整型变量,用于描述数组下标。下标小于或等于i的元素的值,小于或等于枢轴元素的值
j:循环控制变量,表示数组元素下标
(1)假设要排序包含n个元素的数组,请给出在各种不同的划分情况下,快速排序的时间复杂度(用 O记号)。最佳情况为(4),平均情况为(5),最坏情况为(6)。
(2)假设要排序的n个元素都具有相同值时,快速排序的运行时间复杂度属于哪种情况? (7)。 (最佳、平均、最坏)
选项
答案
这是一道考查快速排序算法时间复杂度的分析题。当每次能作均匀划分时,算法为最佳情况,此时时间复杂度可以通过计算递归式T(n)=2T(n/2)+O(n),得到时间复杂度为O(nlogn)。当每次为极端不均匀划分时,即长度为n的数组划分后一个子数组为n-1,一个为0,算法为最坏情况,此时时间复杂度可以通过计算递归式T(n)=T(n-1)+O(n),得到时间复杂度为O(n2)。 对于平均情况的分析较为复杂,假设数组每次划分为9/10:1/10,此时时间复杂度可以通过计算递归式 T(n)=T(9/10)+T(1/10)+O(n),得到时间复杂度为O(nlogn),因此在平均情况下快速排序仍然有较好的性能,时间复杂度为O(nlogn)。 当所有的n个元素具有相同的值时,可以认为数组已经有序,此时每次都划分为长度为n-1和0的两个子数组,属于最坏情况。
解析
转载请注明原文地址:https://kaotiyun.com/show/a0DZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
有关评估系统效率质量特性,以下论述正确的是______。A.响应时间越长,系统执行效率越高B.响应时间和交易执行吞吐量都是用来衡量系统执行快慢的C.响应时间越短,交易执行吞吐量越大D.系统的访问量越大,交易执行吞吐量越大
在各种不同的软件需求中,(36)描述了用户使用产品必须要完成的任务,可以用UML建模语言的(37)表示。(37)
“面向对象技术中,类之间共享属性与行为的机制称为()。
针对下列程序段,需要(58)个测试用例可以满足分支覆盖的要求。intIsLeap(intyear){if(year%4==0){if((year%100==0){
POP3协议采用(29)模式进行通信,当客户机需要服务时,客户端软件与POP3服务器建立(30)连接。(30)
在IPv4向IPv6的过渡期间,如果要使得两个IPv6结点可以通过现有的IPv4网络进行通信,则应该使用(27);如果要使得纯IPv6结点可以与纯IPv4结点进行通信,则需要使用(28)。(27)
若某文件系统的目录结构如下图所示,假设用户要访问文件f1.java,且当前工作目录为Program,则该文件的全文件名为(24),其相对路径为(25)。 (24)
假设某公司营销系统有营销点关系S(营销点,负责人姓名,联系方式)、商品关系P(商品名,条形码,型号,产地,数量,价格),其中,营销点唯一标识S中的每一个元组。每个营销点可以销售多种商品,每一种商品可以由不同的营销点销售。关系S和P的主键分别为(15),S
软件缺陷通常是指存在于软件之中的那些不希望或不可接受的偏差,以下关于软件缺陷的理解不正确的是()。
开发专家系统时,通过描述事实和规则由模式匹配得出结论,这种情况下适用的开发语言是(19)。
随机试题
Onbehalfofboardofdirectors,Iappreciateyouforprovidingthe______________information.
中国共产党的思想路线
Studiesconfirmedthatthiseyediseasewas______intropicalcountries.
主动脉弓从右到左发出的分支依次是
A.易复性疝B.难复性疝C.嵌顿性疝D.绞窄性疝E.滑动性疝站立时肿块变大,平卧后肿块变小
失眠:睡眠:嗜睡
设计任务:请阅读下面学生信息和语言素材,设计20分钟的读写教学方案。教案没有固定格式,但须包含下列要点:.teachingobjectives.teachingcontents.keyanddifficultp
班集体在育人方面突出价值的实现是通过()。
情感具有稳定性、________、持久性的认识活动特征,它往往与人的思想观念紧密相连。
Inmany______alackofdirectionpromptedtheRepublicanGuardtocallitaday.
最新回复
(
0
)