GESP 五级 · GESP 202409 C++ 五级 第 12 题

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

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

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

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

1. 考纲定位：GESP 五级"算法与数据结构"模块，命题人卡住对分治"分解-解决-合并"三要素理解不深的考生，这类题是区分只会背结论和真正懂算法思想的第一道门槛。

2. 解题思维：看到"分治算法"先想定义——把大问题拆成同类型子问题、递归求解、合并结果，这是分治三要素。A 直接对应定义，正确；B 说归并排序不是分治，显然错，归并排序是经典分治；C 说通常用于小规模，分治恰恰适合大规模；D 说时间复杂度总是优于 O(n log n)，分治最坏是 O(n log n)，比如归并、快速排序平均 O(n log n) 但最坏 O(n²)，所以 D 错。

3. 陷阱拆解：B 偷换概念，把归并排序排除；C 用"通常"误导，忽略分治的规模优势；D 用"总是"绝对化，忽略最坏情况。最阴险的是 D，很多学生只记"分治快"，不记得复杂度界限。如果你只背结论、不理解本质，就会掉进这个陷阱。

4. 反命题思维：如果把 D 改成"分治算法的时间复杂度总是 O(n log n)"，答案会变错，因为存在 O(n²) 最坏情况；或者改成"分治算法一定比动态规划快"，会引出不同讨论。刷到类似题时，先问自己"命题人想考我什么"，是理解定义还是考边界。