首页
登录
从业资格
快速排序算法是,在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素
快速排序算法是,在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素
免费题库
2022-08-02
75
问题
快速排序算法是,在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了 ( ) 算法设计策略。已知确定着基准元素操作的时间复杂度为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单列表格()可以根据“分隔符号”分列成多列表格。如果选中某单元格并输入
随机试题
______,heisreadytoacceptsuggestionsfromdifferentsources.A、Insteadofhi
[originaltext]W:Dr.Anderson,couldyoupleaseclarifytherequirementsforth
[originaltext]Man:Lorna,youandyourhusbandopenedthishealthclubherelas
WhichofthefollowingstatementsisNOTtrueaboutthePrimeMinisterinBritai
[originaltext]Youmightthinkthatmostofthepatientsatsleepclinicare
下列关于BIM在项目管理中的应用说法错误的是()。A.在项目实施过程中,各利益相
不属于黄芩蒸或沸水煮的作用是A:使酶灭活B:软化药物C:保存药效D:便于切
原发性高血压最严重的并发症是()。A.脑出血 B.充血性心力衰竭 C.肾功能
以下选项不正确的是()A.1994年以来,我国能源消费增长率与GDP增长
建设工程监理的作用在于()。 A.有利于政府对工程建设参与各方的建设行
最新回复
(
0
)