首页
登录
从业资格
快速排序算法是,在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素
快速排序算法是,在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素
免费题库
2022-08-02
112
问题
快速排序算法是,在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了 ( ) 算法设计策略。已知确定着基准元素操作的时间复杂度为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/2425028.html
本试题收录于:
初级程序员题库软件水平考试初中高级分类
初级程序员
软件水平考试初中高级
相关试题推荐
诊断肺源性心脏病呼吸衰竭最确切的根据是A.白细胞计数及中性粒细胞在感染时增多
关于进行性交后精子穿透力试验,下列哪项是正确的A.应先测基础体温(BBT),根据
属于根据控制内容的覆盖面不同采取的控制措施的是A.质量控制 B.过程控制 C
护士长根据病人情况、护理人员的数量、水平等进行有效组合,体现了护理排班的A.按职
根据相关要求,卫生技术人员需占医院人员总数的A.10% B.50% C.30
抗生素的使用方法不当的是A.根据药动学特征选择抗生素和给药途径 B.病毒感染应
患儿,女,5岁。诊断为化脓性脑膜炎伴营养不良,对其护理下列哪项不正确A.根据患儿
根据患者护理需要编设护理人员属于A.满足患者护理需要原则B.合理结构原则C.优化
Excel单列表格()可以根据“分隔符号”分列成多列表格。如果选中某单元格并输入
Excel单列表格()可以根据“分隔符号”分列成多列表格。如果选中某单元格并输入
随机试题
SOCIALITYINANIMALS(1)Social
I’mgoingtotakethebus______(save)money.tosave非谓语动词。此处需用动词不定式在句中作目的状语。[例句
TheEndoftheCashEraInthespringAdamSmithwillrep
A. B. C. D.
在一些人甚至包括教育界内部的一部分人的心目中.对于历史学科的价值与功能的认识上,
诊断溶血性贫血最可靠的指标是( )。A.骨髓幼红细胞增生 B.异形红细胞增多
以下选项中的工具或应用所依据的科学原理与其他三项不同的是()A.温度计
根据投诉的性质不同,分为()。A:有效投诉和无效投诉B:来人投诉、来函投诉、
下列关于税率的说法中,正确的有()。A.比例税率分为产品比例税率、行业比例
下列情形中,符合法律规定的是()。A.小李与某公司订立的劳动合同约定试用期工资
最新回复
(
0
)