首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下面是快速排序的伪代码,请将空缺处(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
69
问题
下面是快速排序的伪代码,请将空缺处(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
软件设计师下午应用技术考试
软考中级
相关试题推荐
计算机的用途不同,对其部件的性能指标要求也有所不同。以科学计算为主的计算机,对(1)要求较高,而且应该重点考虑(2)。
下图是一个软件项目的活动图,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,则里程碑(49)没有按时完成会影响整个项目的进度。若活动0→2完成后,停止3天才开始活动2→6,则完成整个项目的最少时间是(50)天。(50)
下图为某设计模式的类图,类State和Context的关系为(49),类(50)是客户使用的主要接口。(49)
在面向对象技术中,(43)是一组具有相同结构、相同服务、共同关系和共同语义的(44)集合,其定义包括名称、属性和操作。(44)
在分层体系结构中,(41)实现与实体对象相关的业务逻辑。在基于Java,EE技术开发的软件系统中,常用(42)技术来实现该层。(41)
某公司采用的软件开发过程通过了CMM2认证,表明该公司(30)。
以下关于汇编语言的叙述中,错误的是______。A.汇编语言源程序中的指令语句将被翻译成机器代码B.汇编语言的指令语句必须具有操作码字段,可以没有操作数字段C.汇编程序以汇编语言源程序为输入,以机器语言表示的目标程序为输出D.汇编程序先将源程序中的
对高级语言源程序进行编译时,可发现源程序中的(21)错误。
计算机各功能部件之间的合作关系如下图所示。假设图中虚线表示控制流,实线表示数据流,那么a、b和c分别表示(5)。
随机试题
阀门的密封圈常用的材料有()、合金钢、塑料等。
急性胰腺炎诊断中具有特征性的临床指标是
A、摇动B、扭转C、分根D、去骨E、分冠拔除下颌中切牙主要使用的方法是
行政法规的名称通常为()。
()是一种越来越重要的利率风险,源于银行资产,负债和表外业务中所隐含的期权。
以下关于审计档案的表述中,不恰当的是()。
ThetownIliveinisabouttoputcamerasatalltrafficlightstocatchpeoplewhorunredlights.It【C1】______meofhowmany
某单位周一至周五为工作日,周六、周日双休,某年7月,该单位员工小刘共出勤22天(全勤),则该年的7月8日可能为:
填入下列横线处的词语,最恰当的是()。在物联网、云计算等新技术日趋进步之时,管理软件厂商如何提升自身的市场洞察力和创新能力已经__________。填入画横线部分最恰当的一项是()。
历史研究法主要是用来描述具体的历史事件或历史人物的一种方法。
最新回复
(
0
)