首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了_______算法
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了_______算法
admin
2019-07-12
23
问题
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了_______算法设计策略。已知确定着基准元素操作的时间复杂度为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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在存储体系中位于主存与CPU之间的高速缓存(Cache)用于存放主存中部分信息的副本,主存地址与Cache地址之间的转换工作________________。
下面算法中,不属于公开密钥加密算法的是(45)。
ATM网络采用了许多通信量管理技术以避免拥塞的出现,其中(34)是防止网络过载的第一道防线。
软件开发中的瀑布模型典型地刻画了软件生存周期的阶段划分,与其最相适应的软件开发方法是(9)。
阅读下列说明和算法,回答问题1和问题2,将解答填入答题纸的对应栏内。[说明]算法2-1是用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号或者右括号,则给出相应的提示信息,如下所示:文件提示信息(
图3-2是该系统类图的一部分,依据上述说明中给出的术语,给出类Lock的主要属性。组装(composition)和聚集(aggregation)是UML中两种非常重要的关系。请说明组装和聚集分别表示什么含义?两者的区别是什么?
根据E-R图中给出的词汇,按照“关系模式名(属性,属性,…)”的格式,将此E-R图转换为4个关系模式,并指出每个关系模式中的主码和外码,其中模式名根据需要取实体名或联系名。创建Customers表时,cid使用INTEGER数据类型,cnarne使用
随机试题
企业提前支付了厂房的租金,企业资产负债表的变化是()。
商业银行的存贷比应当不高于()。
国有独资公司为()。
世界500强企业对优秀员工提出了12条核心标准,其中一条是“不找任何借口”。其意思是()。
某花店每天以每枝5元的价格从农场购进若干枝玫瑰花,然后以每枝10元的价格出售。如果当天卖不完,剩下的玫瑰花作垃圾处理。下表所示为花店记录的连续100天玫瑰花的日需求量,若花店每天购进17枝玫瑰花,依此过去100天的需求量推算,当天利润不少于75元的概率为:
国际金融危机的成因不包括()。
2008年以来,索马里附近海域先后发生累计逾120起的海盗劫船事件。海盗为何如此猖獗?甲乙丙丁四人有如下断定:甲:海盗猖獗的主因是被劫船只的船主通常都愿支付高额赎金。乙:如果海盗猖獗的主因是被劫船主愿支付高额赎金,那么肯定会助长海盗的气
设一个学生关系为S(学生号,姓名),课程关系为C(课程号,课程名),选课关系为x(学生号,课程号,成绩),求出所有选课的学生信息的运算表达式为______与______的自然连接。
A、I’mfromShanghai.B、Icomeheretostudy.C、Sorry,Ican’ttellyou.D、Youcan’task.A本题的关键部分是“wheredoyoucomefrom?”意为“你来自
TheInternetandcellphonesarebringingpeopletogether,not【C1】______usapart—atleast,accordingtoanewsurveyrecentlyby
最新回复
(
0
)