分治思想

学习目标

本节学习分治思想。

分治不是某一个具体算法，而是一种解决问题的框架。它的核心是把一个大问题拆成若干规模更小、结构相似的子问题，分别解决后再把结果合并起来。

分治通常包含三个阶段：

这三个阶段分别对应英文中的 divide、conquer 和 combine。

分治通常会使用递归实现，但递归不一定都是分治。

例如，阶乘递归每次只拆成一个更小的问题：

factorial(n) = n * factorial(n - 1)

它是递归，但不是典型分治。

而归并排序会把数组拆成左右两半，分别排序，再合并两个有序结果。这种“拆成多个子问题再合并”的过程更符合分治思想。

分治适合具有以下特点的问题：

常见分治算法包括：

分治算法的复杂度通常来自两部分：

例如，归并排序会把数组分成两半，并且每一层合并都需要处理所有元素。它的时间复杂度可以粗略理解为：每层处理 $n$ 个元素，一共有大约 $\log n$ 层，因此总复杂度是 $O(n \log n)$ 。

这个结论后续会在归并排序小节中进一步解释。

分治的优势在于把复杂问题拆成更容易处理的小问题。

当问题规模较大时，直接解决可能很困难；但如果能拆成结构相同的小问题，就可以用递归自然表达。每一层只关心当前如何拆分和如何合并，不需要一次性处理全部复杂度。

这种思想非常适合树状展开的问题结构。

分治也有代价。

递归会带来调用栈开销，拆分和合并也可能需要额外空间。如果子问题之间存在大量重复，普通分治可能会重复计算，这时可能需要动态规划或记忆化搜索来优化。

因此，使用分治前也要分析问题是否真的适合拆分，以及拆分后的子问题是否能高效合并。

分治是一种把大问题拆成小问题、分别解决、再合并结果的算法思想。

它通常通过递归实现，适合子问题结构与原问题相似、子问题相对独立、结果可以合并的问题。二分查找、归并排序和快速排序都是理解分治思想的重要例子。