首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下面是快速排序的伪代码,请将空缺处(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
24
问题
下面是快速排序的伪代码,请将空缺处(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
软件设计师下午应用技术考试
软考中级
相关试题推荐
()不属于程序的基本控制结构。
采用瀑布模型进行系统开发的过程中,每个阶段都会产生不同的文档。以下关于产生这些文档的描述中,正确的是(25)。
在各种不同的软件需求中,(36)描述了用户使用产品必须要完成的任务,可以用UML建模语言的(37)表示。(37)
采用插入排序算法对n个整数排序,其基本思想是:在插入第i个整数时,前i-1个整数已经排好序,将第i个整数依次和第i-1,i-2,…个整数进行比较,找到应该插入的位置。现采用插入排序算法对6个整数{5,2,4,6,1,3}进行从小到大排序,则需要进行(31)
以下关于数据流图的叙述中,不正确的是()。
数据库系统通常采用三级模式结构:外模式、模式和内模式。这三级模式分别对应数据库的__________。
A类网络是很大的网络,每个A类网络中可以有(26)个网络地址。实际使用中必须把A类网络划分为子网,如果指定的子网掩码为255.255.192.0,则该网络被划分为(27)个子网。(26)
某企业生产流水线M共有两位生产者,生产者甲不断地将其工序上加工的半成品放入半成品箱,生产者乙从半成品箱取出继续加工。假设半成品箱可存放n件半成品,采用PV操作实现生产者甲和生产者乙的同步可以设置三个信号量S、S1和S2,其同步模型如下图所示。 信号量
假设磁盘块与缓冲区大小相同,每个盘块读入缓冲区的时间为10μs,由缓冲区送至用户区的时间是5μs,系统对每个磁盘块数据的处理时间为2μs。若用户需要将大小为10个磁盘块的Docl文件逐块从磁盘读入缓冲区,并送至用户区进行处理,那么采用单缓冲区需要花费的时间
与XY(即X与Y不相同时,XY的结果为真)等价的逻辑表达式为________________。
随机试题
下列致病菌和慢性龈炎无关的是()
脾为气血生化之源的理论基础是
肾病综合征临床四大特点是
对于美国在海外的公司,以下四个选项中哪项是《美国海外贪腐防治法》所允许的。
直接利用年金现值系数计算投资项目内含收益率所要求的前提条件有()。
教师指导学生阅读巴金的小说《家》时,分析了其中觉新这个“多余人”的形象,还提及中国文学中其他“多余人”的形象,下列不属于这一形象的是()。
张啸这次考试成绩非常差,老师找他谈话时,他分析原因是因为近期喜欢上班内一名女同学,上课经常开小差学习不够努力。这种归因属于()。
Beingsociablelookslikeagoodwaytoaddyearstoyourlife.Relationshipswithfamily,friends,neighbours,evenpets,will
Americanwomenwilloccasionallywearshortskirts,sleevelessshirts,makeup,perfume,mightevenshowsomecleavage:she’sju
Fromchildhoodtooldage,wealluselanguageasameansofbroadeningourknowledgeofourselvesandtheworldaboutus.When
最新回复
(
0
)