首页
登录
从业资格
快速排序算法是,在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素
快速排序算法是,在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素
免费题库
2022-08-02
119
问题
快速排序算法是,在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了 ( ) 算法设计策略。已知确定着基准元素操作的时间复杂度为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://www.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单列表格()可以根据“分隔符号”分列成多列表格。如果选中某单元格并输入
随机试题
Exercisehaslongbeentreatedasthecure-allforeverythingthatailsyou.
Fourin10teachershavefacedverbalorphysicalaggression(袭击)fromapu
一家技术研究机构指出,全球范围个人电脑销量持续下降,而平板电脑正在取代个人电脑成为许多人的主要电脑装置。2013年第二季度的全球个人电脑出货量与去年同比
4根材料和截面面积相同而截面形状不同的匀质梁,其抗弯能力最强的是()截面的梁
主板上市公司,以下不可以进行非公开发行的有( )A.上市公司权益被控股股东严重
违反投资适当性原则的主要原因在于() Ⅰ.投资者并不一定能够掌握有关产品的充分
船舶装卸平衡原理所提出的装卸作业的平衡是指( )的平衡。A.各舱口装卸机械和人
石油化工企业是以石油、天然气及其产品为原料,生产、储运各种石油化工产品的炼油厂、
“骆驼”评价体系的主要内容是通过对金融机构“资本的充足程度、资产质量、管理水平、
工序质量的控制,可以简单归纳为()的管理控制循环系统。A.实施-检査-处理-总结
最新回复
(
0
)