首页
登录
从业资格
快速排序算法是,在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素
快速排序算法是,在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素
免费题库
2022-08-02
53
问题
快速排序算法是,在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了 ( ) 算法设计策略。已知确定着基准元素操作的时间复杂度为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单列表格()可以根据“分隔符号”分列成多列表格。如果选中某单元格并输入
随机试题
Itishightimethatthisargument(put)______anendto.wereput本题测试的是虚拟语气的用法。
预期()时,投资者应考虑卖出看涨期权。A、标的物价格上涨且大幅波动B、标的物市场处于熊市且波幅收窄C、标的物价格下跌且大幅波动D、标的物市场处于牛
[originaltext]Mrs.Joneswasovereighty,butshestilldroveheroldcarl
用灌砂法测定压实度时,试验报告中各种材料的干密度均应精确至0.01g/cm3。(
A、0、88 B、1、02 C、0、43 D、0、91
幼儿园教育是基础教育的重要组成部分,是学校教育制度的预备阶段。
下列选项中,中国传统写意花鸟画特有的画法是()。A.罩染 B.点厾 C.
梦想是什么? 在卖火柴的小女孩眼里,梦想是飘香的烤鹅,是奶奶温暖的双臂;在“千
健康是指人( )的健全状态。A.心理与社会适应 B.心理适应 C.身体与心
1962年,美国女作家雷切尔·卡逊出版《寂静的春天》,引起对( )。A.热带雨
最新回复
(
0
)