首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了_______算法
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了_______算法
admin
2019-07-12
22
问题
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了_______算法设计策略。已知确定着基准元素操作的时间复杂度为O(n),则快速排序算法的最好和最坏情况下的时间复杂度为_______ 。
(62)
选项
A、O(n)和O(nlgn)
B、O(n)和O(n
2
)
C、O(nlgn)和O(nlgn)
D、O(nlgn)和O(n
2
)
答案
D
解析
将数据分成若干份,每份单独处理后再合并,其思想为分治。理想情况下,快速排序每次将数据划分为规模相近的两部分,并递归至不可再划分,因此其时间复杂度为O(nlgn)。在最坏情况下,每次划分都极不均匀,如一个类别中仅有一个元素,另一个类别中包含剩余所有元素。这时划分的复杂度为0(n),n次操作的总复杂度为O(n
2
)。
转载请注明原文地址:https://kaotiyun.com/show/m2CZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
网络系统设计过程中,物理网络设计阶段的任务是____________。
以太网的数据帧封装如下图所示,包含在IP数据报中的数据部分最长应该是(23)________________字节。
某文件系统采用位示图(bitmap)记录磁盘的使用情况。若计算机系统的字长为64位,磁盘的容量为1024G,物理块大小为4MB,那么位示图的大小需要()个字。
IEEE802.11i所采用的加密算法为__________。(2010年下半年试题)
计算机运行过程中,CPU需要与外设进行数据交换。采用_____________控制技术时,CPU与外设可并行工作。
在需求分析阶段,采用UML的用例图(usecasediagram)描述系统功能需求,如图4-4所示。指出图中的A,B,C和D分别是哪个用例?类通常不会单独存在,因此当对系统建模时,不仅要识别出类,还必须对类之间的相互关系建模。在面向对象建模中,提供
试将[算法2-1)和[算法2-2]中(1)~(7)处补充完整。从下面的选项中选择相应的判断逻辑填补[算法2-2]中的“判断条件1”至“判断条件3”。注意,若“判断条件2”的逻辑判断结果为假,就无需对“判断条件3”进行判断。(a)字符是括号(b
阅读下列说明和算法,回答问题1和问题2,将解答填入答题纸的对应栏内。[说明]算法2-1是用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号或者右括号,则给出相应的提示信息,如下所示:文件提示信息(
图3-2是该系统类图的一部分,依据上述说明中给出的术语,给出类Lock的主要属性。依据上述说明中给出的词语,将图3-3中的(1)~(5)处补充完整。
随机试题
Mr.Harrisdecidedtoopenanewstoreand______manyclerks.
要素饮食的适应证是【】
涂片的制备时,下列说法不正确的是
与CT图像显示上下位置偏移有关的操作是
医师应怎样全面看待健康与疾病
有权就实施行政许可收取费用作出规定的规范性文件是()。
某计算机采用16位定长指令字格式,其CPU中有一个标志寄存器,其中包含进位/借位标志CF、零标志zF和符号标志NF。假定为该机设计了条件转移指令,其格式如下:其中,00000为操作码OP;C、Z和N分别为CF、ZF和NF的对应检测位,某检测位为1时表示
下列各选项中的两函数相等的是().
A、 B、 C、 D、 A照片中有一群人在室内,有一个看着前面电脑的女性的背影,因此正确答案是(A)项。尽管照片中有很多客人(customers),但是有很多空座位。因此(B)项是错误的。如果听到librar
FrommyinfancyIwasnotedforthedocilityandhumanityofmydisposition.Mytendernessofheartwasevensoconspicuousast
最新回复
(
0
)