在n个数的数组中确定其第i(1≤i≤n)小的数时,可以采用快速排序算法中的划分思想,对n个元素划分,先确定第k小的数,根据i和k的大小关系,进一步处理,最终得到第i小的数。划分过程中,最佳的基准元素选择的方法是选择待划分数组的(64)元素。此时,算法在最坏情况下的时间复杂度为(不考虑所有元素均相等的情况)(65)。
2023-09-01
B.Θ(lgn)
C.Θ(nlgn)
D.Θ(n2)
参考答案:D
本题考查数据结构基础知识。快速排序一种分治的排序方法,其思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。快速排序的每一趟结果都是找到一个基准元素放置于线性表中部位置,将原来的线性表划分为前后两部分,前部分元素都小于基准元素,后部分元素都大于基准元素。快速排序总的关键字比较次数为Θ(nlog2n),最坏情况下时间复杂度为Θ(n2),最好情况下的时间复杂度为Θ(nlog2n);快速排序是不稳定的排序。最坏情况下需要的栈空间为Θ(n),其他需要Θ(nlog2n)。根据以上描述,本题依次选C、D选项。
2023-05-23 从业资格其它
2023-05-23 从业资格其它
影响动机产生的因素包括( ) (A)内驱力 (B)诱因(C)外归因 (D)情绪
2023-05-23 从业资格其它
病理性遗忘的种类包括( )遗忘。 (A)倒错性 (B)顺行性(C)逆行性(D)错构性
2023-05-23 从业资格其它
热门标签