GESP 五级 · GESP 202403 C++ 五级 第 21 题

分治算法的典型应用之一是归并排序，其时间复杂度为 $O(N \log N)$。

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

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

【考点】分治策略｜归并排序｜复杂度分析

1. 🎯 考纲定位

• 本题考查《GESP 五级算法与程序设计》中"分治策略"与"复杂度分析"交叉点
• 命题人专卡学生"记住名字≠理解复杂度"的弱点：六级才要求推导 T(N)=2T(N/2)+N，五级直接考结论
• 这道题就是看你是否把"归并排序"和"O(N log N)"绑定成肌肉记忆

2. 🧠 解题思维

• 看到"分治"先想：把大问题拆成 N/2 个子问题，每层合并仍需 O(N)
• 合并步骤固定：无论数组多乱，合并两个有序子表总花 N 次比较
• 递归深度 log N，每层总工作量 N，总和 N log N
• 通法：任何"分治 + 线性合并"的算法，复杂度必为 O(N log N)（如快排平均情况）

3. 🪤 陷阱拆解

• A 项正确，但很多人会选 B：把归并排序和冒泡/选择排序混淆，误以为"排序"就是 O(N²)
• 命题人利用"名字陷阱"：只记"归并排序"四个字，不记得它用了"分而治之"
• 最阴险的细节：题干说"典型应用之一"，暗示还有其他分治应用（如快速排序），但复杂度不同——快排平均 O(N log N) 最坏