首页
登录
从业资格
在n个数的数组中确定其第i(1≤i≤n)小的数时,可以采用快速排序算法中的划分思
在n个数的数组中确定其第i(1≤i≤n)小的数时,可以采用快速排序算法中的划分思
最全题库
2022-08-02
49
问题
在n个数的数组中确定其第i(1≤i≤n)小的数时,可以采用快速排序算法中的划分思想,对n个元素划分,先确定第k小的数,根据i和k的大小关系,进一步处理,最终得到第i小的数。划分过程中,最佳的基准元素选择的方法是选择待划分数组的( )元素。此时,算法在最坏情况下的时间复杂度为(不考虑所有元素均相等的情况)( )。问题1选项A.第一个B.最后一个C.中位数D.随机一个问题2选项A.Θ(n)B.Θ(lgn)C.Θ(nlgn)D.Θ(n2)
选项
答案
CA
解析
本题考查算法设计与分析的相关知识。
中位数的含义:将一组数据按照由小到大(或由大到小)的顺序排列,如果数据的个数是奇数,则处于中间位置的数就是这组数据的中位数;如果数据的个数是偶数,则中间两个数据的平均数就是这组数据的中位数。根据题干的描述,选择的基准元素将数组分得越均匀越好,因此中位数是最佳选择。
对于该问题,若每次都是选择中位数作为基准元素,则时间复杂度的递归式为:
T(n)=T(n/2)+cn
求解该递归式,得到T(n)=Θ(n)。
这里的时间复杂度,可以理解为:由于选择的是中位数,每轮比较最多只需要比较n/2次后,所有元素就可以完成对应的一轮排序。所以第一轮比较的次数可以考虑为n/2;第2轮比较的次数可以考虑为对2侧分别比较n/4次,直到最终比较完成。时间复杂度的紧致界限为Θ(n)。
转载请注明原文地址:https://tihaiku.com/congyezige/2410376.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
在信息管理中,哪些是信息进行加工处理的最基本方式:__()__①变化、排序、核
DES是一种(请作答此空)加密算法,其密钥长度为56位,3DES是基于DES的加
在数据库设计中,下列步骤排序正确的选项是()。 ①需求分析 ②物理结构设
在一个数据库中,如果要赋予用户userA可以查询department表的权限,应
()算法是不稳定的排序算法。A.简单选择 B.冒泡 C.直接插入 D.归
关于二叉排序树的说法,错误的是( )。A.对二叉排序树进行中序遍历,必定得到结
海明校验码是在n个数据位之外增设k个校验位,从而形成一个k+n位的新的码字,使新
根据历史数据,确定一个就诊人员是否可能患心脏病,可以采用( )算法。A.C4.
关于聚类算法K-Means和DBSCAN的叙述中,不正确的是( )。A.K-M
聚类的典型应用不包括( ),( )是一个典型的聚类算法。 问题1选项 A
随机试题
Shewasstandingoutsideinthesnow,_______withcold.A、spinningB、shiveringC、
Themillionsofcalculationsinvolved,______byhand,wouldhavelostallpract
Iamstillunabletomakemyself(understand)______whencommunicatingwithfore
In1812,inavillagenearParis,alittleboyhithimselfintheeyewitho
[originaltext]W:Nowyou’veseenthistableoffiguresaboutthepocketmoneyc
制定质量监督工作方案,确定负责该项工程的质量监督工程师和助理质量监督师。
我国文化产业快速发展,对经济增长的贡献率也逐步提升。下列属于文化产业的是____
新生儿败血症体温过高时应A.调节室内温度,松解包被 B.按医嘱给予退热剂 C
一位年轻的未婚妇女因子宫出血过多住院。患者主诉子宫出血与她的月经有关,去年就发生
下述各项中,影响跑道长度的主要因素有( )。A.机场的基准温度 B.飞机
最新回复
(
0
)