2. 从业资格
  3. 在n个数的数组中确定其第i(1≤i≤n)小的数时，可以采用快速排序算法中的划分思

在n个数的数组中确定其第i(1≤i≤n)小的数时，可以采用快速排序算法中的划分思

最全题库2022-08-02  41
问题 在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
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)