首页
登录
从业资格
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待
admin
2022-08-02
84
问题
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了( 此空作答 )算法设计策略。已知确定着基准元素操作的时间复杂度为 O(n) ,则快速排序算法的最好和最坏情况下的时间复杂度为()。A.分治B.动态规划C.贪心D.回溯
选项
A.分治
B.动态规划
C.贪心
D.回溯
答案
A
解析
将数据分成若干份,每份单独处理后再合并,其思想为分治。 理想情况下,快速排序每次将数据划分为规模相近的两部分,并递归至不可再划分,因此其时间复杂度为 O(nlgn) 。在最坏情况下,每次划分都极不均匀,如一个类别中仅有一个元素,另一个类别中包含剩余所有元素。这时划分的复杂度为 O(n) , ” 次操作的总复杂度为 O(n2)
转载请注明原文地址:https://tihaiku.com/congyezige/2408353.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
假定某企业根据2014年5月员工的出勤率、岗位、应扣款得出的工资表如下:
假定某企业根据2014年5月员工的出勤率、岗位、应扣款得出的工资表如下:
假定某企业根据2014年5月员工的出勤率、岗位、应扣款得出的工资表如下:
对n个关键码构成的序列采用简单选择排序法进行排序的过程是:第一趟经过n-1次关键
CPU执行指令时,先要根据程序计数器将指令从内存读取出并送入( ),然后译
给定包含n个正整数的数组A和正整数x,要判断数组A中是否存在两个元素
有两个N*N的矩阵A和B,想要在微机(PC机)上按矩阵乘法基本算法编程实现计
银行系统数据流图中,某个加工根据客户的多个不同属性的值来执行不同的操作,则对该加
设数组a[1…n,1…m](n>1,m>1)中的元素以行为主序存放,每个元素占用
设数组a[1…10,1…8]中的元素按行存放,每个元素占用4个存储单元,已知第一
随机试题
[originaltext]M:Hello.MattEllisspeaking.W:Hello,Dr.Ellis,myname’sPam
WilliamWrigleyJr.,theAmericanchewing
脚手架工程必须有完善的施工方案,并经企业技术负责人审批。并且有完善的安全防护措施
某新建项目,建设期3年,分年度贷款,第一年贷款600万元,第二年贷款900万元,
下列影响因素中,不属于商标资产价值影响因素的是()。A.宏观经济状况 B
把下列的六个图形分为两类,使每一类图形都有各自的共同特征或规律,分类正确的一项是
升麻的功效是A.发表透疹、清热解毒、升举阳气 B.疏散风热、清利头目、祛风止痛
下列不属于离岸金融中心的类型的是()。A.巴哈马型中心 B.避税港型中心
自用工之日起1个月内,经用人单位书面通知后,劳动者不与用人单位订立书面劳动合同,
会计工作岗位可以一人一岗、一人多岗,但不得多人一岗,避免互相推诿、人浮于事,降低
最新回复
(
0
)