GESP 七级 · GESP 202603 C++ 七级 第 20 题

使用归并排序对 $n$ 个元素进行排序时，无论最好、最坏还是平均情况，时间复杂度均为 $O(n \log n)$ 。

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

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

【考点】归并排序｜时间复杂度｜分治算法

1. 🎯 考纲定位 本题考查《GESP 202603 C++ 七级》算法基础模块中的【归并排序】与【时间复杂度】。命题人专卡考生对"分治算法复杂度稳定性"的盲点——绝大多数人只记得最坏情况，却误以为最好、平均会退化，这道题就是用来清除这个误区的。

2. 🧠 解题思维 归并排序是典型的分治算法：把数组分成两半递归排序，再合并。关键在于合并过程：无论输入序列是否有序，合并两个已排序子数组都需要线性扫描，耗时 $O(n)$。递归深度是 $\log n$，总耗时 $T(n) = 2T(n/2) + O(n) = O(n \log n)$。因此最好、最坏、平均三种情况都严格等于 $O(n \log n)$，不可能出现 $O(n)$ 或 $O(n^2)$。

3. 🪤 陷阱拆解 错误选项 B 的设计意图是利用"快速排序最好情况 $O(n \log n)$、最坏 $O(n^2)$"的对比，让考生误以为归并排序也有类似波动。但归并排序的合并步骤是固定的，不受输入顺序影响，因此复杂度恒定。题目中"无论最好、最坏还是平均情况"的表述是绝对化的，如果考生只背结论而不理解算法流程，就会在"平均情况"上产生怀疑，从而选错。

4. 🔄 反命题思维 命题人若把题干改成"归并排序最好情况是 $O(n)$"，答案就立刻反转为 B，因为合并过程无法避免线性开销。或者改成"冒泡排序最好情况是 $O(n)$"，答案仍为 A，但考点变成"排序算法最优性能"。这类变式题在七级试卷中常用来区分"死记硬背"与"理解本质"的考生。