GESP 六级 · GESP 六级样题（C++ 组） 第 3 题

关于分治算法，下列说法错误的是（ ）。

这题考分治算法的核心概念与时间复杂度。直接判断各选项正误，C 错在把二分查找的 O(log N) 偷换成所有分治算法的复杂度，这是命题人最爱挖的坑，看到 C 这种绝对化表述先打问号。

学生最容易错选 C，因为背过二分查找是 O(log N)，就下意识以为所有分治都是对半拆分所以也是 O(log N)。其实分治算法的时间复杂度由递归式决定，合并排序、归并排序、快速排序平均都是 O(N log N)，只有二分查找、折半搜索等少数是 O(log N)。若题目问“下列分治算法时间复杂度为 O(log N) 的是”，那 C 就对了，但这里问的是“分治算法的时间复杂度是 O(log N)”，以偏概全，必须警惕这种过度概括的陷阱。

考点定位

本题考查分治算法的核心思想、实现方式及时间复杂度规律，属于算法基础中的高频考点。

概念与命题视角

分治算法的本质是“分而治之”：将规模较大的问题分解为若干个规模较小、相互独立且与原问题形式相同的子问题，递归求解子问题，最后将子问题的解合并得到原问题的解。

命题人在这里设下的陷阱非常典型：利用学生熟悉二分查找的 $O(\log N)$ 复杂度，诱导学生产生“所有分治算法都是 $O(\log N)$”的错误联想。事实上，分治算法的时间复杂度取决于分解后的子问题规模、子问题个数以及合并步骤的代价，由递归式 $T(N) = aT(N/b) + f(N)$ 决定，而非单纯看是否“对半拆分”。