首页
登录
从业资格
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待
资格题库
2022-08-02
85
问题
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了( )算法设计策略。已知确定着基准元素操作的时间复杂度为 O(n) ,则快速排序算法的最好和最坏情况下的时间复杂度为( 此空作答 )。A.O(n)和O(nlgn)B.O(n)和O(n2)C.O(nlgn)和O(nlgn)D.O(nlgn)和O(n2)
选项
A.O(n)和O(nlgn)
B.O(n)和O(n2)
C.O(nlgn)和O(nlgn)
D.O(nlgn)和O(n2)
答案
D
解析
将数据分成若干份,每份单独处理后再合并,其思想为分治。 理想情况下,快速排序每次将数据划分为规模相近的两部分,并递归至不可再划分,因此其时间复杂度为 O(nlgn) 。在最坏情况下,每次划分都极不均匀,如一个类别中仅有一个元素,另一个类别中包含剩余所有元素。这时划分的复杂度为 O(n) , ” 次操作的总复杂度为 O(n2) 。
转载请注明原文地址:https://tihaiku.com/congyezige/2408354.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
假定某企业根据2014年5月员工的出勤率、岗位、应扣款得出的工资表如下:
假定某企业根据2014年5月员工的出勤率、岗位、应扣款得出的工资表如下:
风险的优先级通常是根据()设定。A.风险影响(RiskImpact) B.
对n个关键码构成的序列采用简单选择排序法进行排序的过程是:第一趟经过n-1次关键
堆是一种数据结构,分为大顶堆和小顶堆两种类型。大(小)顶堆要求父元素大于等于(小
给定包含n个正整数的数组A和正整数x,要判断数组A中是否存在两个元素
有两个N*N的矩阵A和B,想要在微机(PC机)上按矩阵乘法基本算法编程实现计
通过设置基准(枢轴)元素将待排序的序列划分为两个子序列,使得其一个子序列的元素均
某酒店预订系统有两个重要功能:检索功能和预订功能。检索功能根据用户提供的关键字检
根据《计算机软件保护条例》的规定,著作权法保护的计算机软件是指( )。A.程序
随机试题
LindaStanley’snewfilm______soldoutfortwoweekendsinarow.A、isB、areC、wa
Whatdidthemandolastnight?[br][originaltext]W:Sodidyoudomuchyester
Aprilfool’sDayistraditionallyadaytoplaypracticaljokesonothers,se
每一回路抽查两个扬声器。使任意一个扬声器断路,其他扬声器的工作状态不应受影响。
关于温湿度独立控制空调系统,下列哪些说法是不正确的?()A.新风除湿处理应采
依照《中华人民共和国合同法》,委托开发完成的发明创造,除当事人另有约定的以外,申
自我照顾模式是由谁提出的( )A.纽曼 B.佩普劳 C.汉斯·席尔 D.
A.《药品生产许可证》B.《药品批发许可证》C.《药品经营许可证》D.《药品使用
人生感悟 人类为什么称自己为人,而不称自己为动物,是因为我们一直以来都把自
在个体社会化过程中起关键作用的人或者人群称为()。 (A)抽象化他人(B)
最新回复
(
0
)