GESP 五级 · GESP 202406 C++ 五级 第 10 题

关于分治算法，以下哪个说法正确？

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

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

【考点】分治算法｜高级算法

1. 考纲定位 本题考查《GESP 考试大纲》五级“高级算法”模块中的分治策略定义。命题人把这道题放在五级，是为了卡住还在死记硬背“快排/归并”的考生——他们可能背得出算法名，但说不清分治的本质三步骤。

2. 解题思维 看到题先区分“分治”与“贪心”：分治必须满足“可分解性”（能把大问题拆成相似子问题）。

• A 项：逐字对应“分治三步”（分、治、合），正确。
• B 项：归并排序是典型分治应用（分半→排序→合并），错。
• C 项：分治恰恰适合大规模问题（减少重复计算），错。
• D 项：分治复杂度取决于合并步，最坏可到 $O(n^2)$，错。

3. 陷阱拆解

• B 项陷阱：命题人把“归并排序”这个分治经典案例直接否定，考的是你是否知道它属于分治家族。
• C 项陷阱：偷换“分治”与“分解”的概念——分治是为了解决大规模问题，小问题直接算更划算。
• D 项陷阱：绝对化表述“总是优于 $O(n \log n)$”，命题人想看你是否知道最坏情况（如归并排序的合并步也可能达到 $O(n \log n)$，快速排序最坏 $O(n^2)$）。
• A 项陷阱：很多人背“分治”只记住“快排/归并”，却说不清“分→治→合”三步缺一不可，命题人用这个选项卡死只会背结论的考生。

4. 反命题思维 反命题角度：

• 若把 B 改为“快速排序不是分治算法的应用”，答案仍为 A；若把 C 改为“分治算法通常用于解决大规模问题”，则 C 正确，A 就变成错误选项了——命题人就是在考你对“分治适用范围”的理解。
• D 项若改成“分治算法最坏时间复杂度一定优于 $O(n \log n)$”，命题人想卡住你——归并排序最坏就是 $O(n \log n)$，快速排序最坏 $O(n^2)$，绝对化表述必错。
• 刷到类似题先问自己：“命题人想考我分治的哪一步？”（分、治、合）