2. 计算机
  3. 在n个数的数组中确定其第i(1≤i≤n)小的数时，可以采用快速排序算法中的划分思想，对n个元素划分．先确定第k小的数，根据i和k的大小关系，进一步处理，最终得到第i小的数。划分过程中，最佳的基准元素选择的方法是选择待划分数组的(64)元素。此时，算法在最坏

在n个数的数组中确定其第i(1≤i≤n)小的数时，可以采用快速排序算法中的划分思想，对n个元素划分．先确定第k小的数，根据i和k的大小关系，进一步处理，最终得到第i小的数。划分过程中，最佳的基准元素选择的方法是选择待划分数组的(64)元素。此时，算法在最坏

admin2019-07-12  23
问题 在n个数的数组中确定其第i(1≤i≤n)小的数时，可以采用快速排序算法中的划分思想，对n个元素划分．先确定第k小的数，根据i和k的大小关系，进一步处理，最终得到第i小的数。划分过程中，最佳的基准元素选择的方法是选择待划分数组的(64)元素。此时，算法在最坏情况下的时间复杂度为(不考虑所有元素均相等的情况)(65)。
(65)
选项 A、Θ(n)
B、Θ(lgn)
C、Θ(nlgn)
D、Θ(n2)
答案A
解析 本题考查算法设计与分析的相关知识。中位数的含义：将一组数据按照由小到大(或由大到小)的顺序排列，如果数据的个数是奇数，则处于中间位置的数就是这组数据的中位数；如果数据的个数是偶数，则中间两个数据的平均数就是这组数据的中位数。根据题干的描述，选择的基准元素将数组分得越均匀越好，因此中位数是最佳选择。对于该问题，若每次都是选择中位数作为基准元素，则时间复杂度的递归式为：
T(n)=T(n/2)+cn
求解该递归式，得到T(n)=Θ(n)。
转载请注明原文地址:https://kaotiyun.com/show/khCZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

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