GESP 八级 · GESP 202412 C++ 八级第 18 题

判断题 · 答案 A · 考点：快速排序、归并排序、时间复杂度分析

题目

对 $n$ 个元素的数组进行排序，快速排序和归并排序的平均时间复杂度都为 $O(n \log n)$。但快速排序存在退化情况，使得时间复杂度升高至 $O(n^2)$；归并排序需要额外的空间开销。

答案：A

快速排序归并排序时间复杂度分析

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】快速排序｜归并排序｜时间复杂度

GESP 八级 C++ 算法模块，考察排序算法复杂度。命题人卡住的是"平均 vs 最坏"的辨析——八级考生常把"平均 $O(n \log n)$"误当成"最坏 $O(n \log n)$"，或者看到快速排序的退化就以为整个陈述错误。

第 28 题· NOIP 2008 普及组初赛试题 · 答案 a[left]a[j]<valuea[j]<=valuevalue>a[j]value>=a[j]a[i]>valuea[i]>=valuea[i]=value;i+1,right,nFindKth(left,i-1,n);看解析 →
第 27 题· NOIP 2008 提高组初赛试题 · 答案 a[left];a[j]<valuea[j]<=valuea[i]>valuea[i]>=valuea[i] = value; i + 1,right,n FindKth(left, i – 1, n);看解析 →
第 15 题· NOIP 2009 普及组初赛试题 · 答案 D看解析 →
第 17 题· NOIP 2009 普及组初赛试题 · 答案 D看解析 →
第 8 题· NOIP 2009 提高组初赛试题 · 答案 A看解析 →

在 OI伴学里做这道题

登录后可计时作答、查看完整六段式解析，并按你的错题自动生成同类练习。