首页
登录
从业资格
快速排序算法是,在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素
快速排序算法是,在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素
免费题库
2022-08-02
118
问题
快速排序算法是,在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了 ( ) 算法设计策略。已知确定着基准元素操作的时间复杂度为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单列表格()可以根据“分隔符号”分列成多列表格。如果选中某单元格并输入
随机试题
Forthispart,youareallowed30minutestowritearecommendationletter.
IEEE802.11在MAC层采用了()协议。 A.CSMA/CD B.
不属于盆膈范畴的肌肉及筋膜的项目为A、耻尾肌 B、髂尾肌 C、坐尾肌
下列哪种情况洋地黄剂量宜偏小A.肺心病,心力衰竭 B.房扑 C.风心病,二尖
胎儿娩出后24小时内出血量超过多少为产后出血A.300ml B.800ml
先兆流产概述
开展音乐教育活动的第一步是() A.选择教育内容B.确定教学方法 C.制
关于六西格玛管理的说法,错误的是()。A:六西格玛管理追求完美,绝不容忍失误
葡萄糖通过一般细胞膜属于A.载体中介的易化扩散 B.通道中介的易化扩散 C.
下列不属于公司信贷的接受主体的是()。 A.法人B.经济组织 C.非自然
最新回复
(
0
)