什么是分治算法？分治的三个步骤和适用条件是什么？

简化版

分治（Divide and Conquer）就是把一个大问题拆成若干个规模更小、结构和原问题一样的子问题，递归解决每个子问题，再把子问题的解合并成原问题的解。三步走：分（Divide）→ 治（Conquer）→ 合（Combine）。归并排序、快速排序、二分查找、快速幂都是它的典型应用。它能用的前提是：子问题相互独立（不重叠）、和原问题同构、且子解能合并。

详细版

分治的三个步骤：

分（Divide）：把原问题划分成几个规模更小的同类子问题。
治（Conquer）：递归求解各子问题；当子问题小到一定程度（到达递归基 base case）时直接求解。
合（Combine）：把子问题的解合并，得到原问题的解。

适用的四个条件：

可分解：原问题能分成规模更小、与原问题同构的子问题。
相互独立：子问题之间不重叠、彼此独立——这一条是和动态规划的分水岭（子问题重叠就该用 DP 记忆化）。
可合并：子问题的解能合并成原问题的解，而且合并的代价可控。
有边界：存在可以直接求解的最小子问题（递归出口）。

几个经典例子的差异：

算法	分成几份	活儿主要在哪
归并排序	2 份	合并两个有序半
快速排序	2 份	分区（分的时候就干活，无需合并）
二分查找	只进 1 份	无需合并（严格说是「减治」）
快速幂	只算 1 份再平方	平方合并

分治算法的复杂度通常用递归式 T(n) = a·T(n/b) + f(n) 描述，再用主定理求解（见「主定理」那道题）。

完整版教学

一、分治的三步骤：分、治、合

分治的思想可以用一句朴素的话概括：大问题不好解，就拆成同类的小问题，小的解完再拼回去。 落到操作上永远是三步：

分（Divide）：把当前问题切成几块规模更小的同类子问题。最常见是「对半切」，但也可以切成三份、按某种规则切。
治（Conquer）：对每个子问题递归调用自己。递归总要有出口——当子问题小到可以直接回答（比如只剩一个元素、区间为空）时，不再往下分，直接返回。这个出口叫递归基（base case），漏写它会导致无限递归。
合（Combine）：把子问题的解组合成原问题的解。这一步是分治里最能体现「巧劲」的地方——归并排序难在合并两个有序数组、最近点对难在处理跨中线的点对。

三步里，「分」和「治」往往是套路化的，真正决定一个分治算法难度和效率的，通常是「合并」这一步。

二、什么问题适合分治：四个条件

不是所有问题都能分治，得同时满足四个条件：

问题可以分解成规模更小的同类子问题。 「同类」很关键——子问题必须和原问题是一回事，只是规模更小，这样才能递归地用同一套逻辑解决。
子问题相互独立、不重叠。 各子问题各算各的，不共享、不重复计算。如果子问题会大量重叠（比如斐波那契 f(n)=f(n-1)+f(n-2)，f(n-2) 被反复算），纯分治就会指数级重复计算，这时应该改用动态规划（记忆化）。
子问题的解可以合并成原问题的解。 而且合并本身不能太贵，否则抵消了分治的收益。
存在可直接求解的最小子问题（递归基）。 保证递归能停下来。

记忆点：分治能不能用，先问自己三句话——「能拆成同类的小问题吗？」「小问题之间独立吗？」「小问题的答案拼得回去吗？」三个都「是」，才适合分治。

三、分治 vs 减治：二分查找到底算不算分治

严格的算法教材会把「分治」和「减治（Decrease and Conquer）」区分开：

分治：把问题分成多个子问题，每个都要解，再合并。比如归并排序，左右两半都得排。
减治：每步只把问题缩小到一个子问题，只解其中一个，无需合并。比如二分查找，每次只在左半或右半里继续找，另一半直接丢掉。

按这个严格定义，二分查找、快速幂本质是「减治」。但工程和多数面试语境里，大家习惯把它们也归到广义的分治里——因为它们都体现了「把问题规模成倍缩小」的分治精神。面试时你能点出这个区别，是加分项；不必纠结叫法。

四、分治 vs 动态规划：子问题是否重叠是分水岭

这是最容易混、也最爱考的对比：

	分治	动态规划
子问题关系	相互独立、不重叠	相互重叠（同一个子问题被反复需要）
是否记忆化	不需要（算过不会再要）	需要（用表存下来避免重算）
典型例子	归并、快排、快速幂	背包、最长公共子序列、斐波那契

一句话抓本质：子问题独立用分治，子问题重叠用动态规划。 动态规划可以看成「带记忆化的、子问题会重叠的分治」。判断标准就是——画出递归树，如果同一个子问题在树里出现多次，就该上 DP。

五、分治的复杂度怎么算：递归式 + 主定理

分治算法的运行时间天然是递归式：

T(n) = a · T(n/b) + f(n)

含义是：把规模 n 的问题分成 a 个规模 n/b 的子问题（a·T(n/b)），再花 f(n) 的代价去「分」和「合」。

归并排序：分 2 份、各半、合并 O(n) → T(n) = 2T(n/2) + O(n)，解得 O(n log n)。
二分查找：只进 1 份、减半、O(1) → T(n) = T(n/2) + O(1)，解得 O(log n)。

这类递归式用主定理（Master Theorem） 就能一眼算出复杂度，细节见专门那道题。

六、常见误区

❌ 以为「递归就是分治」——递归只是实现手段，分治是「分成多个独立子问题再合并」的思想；很多递归（如回溯、DFS）并不是分治。
❌ 把子问题会重叠的问题硬套分治——会指数级重算，那类问题该用动态规划。
❌ 忘写递归基导致无限递归——每个分治都必须有能直接返回的最小子问题。
❌ 以为分治一定更快——如果合并代价太高，分治未必优于直接解法（如最大子数组的分治 O(n log n) 就不如 Kadane 的 O(n)）。

七、递归式、合并证明与数字推演

这道题的分治闭环是：子问题与原问题同构、规模严格缩小，并能在有限代价内合并。递归调用只保证子问题正确，原问题能否正确仍取决于合并步骤是否覆盖所有情况且不重不漏。

T(n)=aT(n/b)+f(n)
递归树核对：每层子问题数 × 单个子问题的非递归代价

带数字推演：归并把 8 个元素拆到单元素共 3 层，每层合并总工作量 8，所以为 8×3。推演时应记录每层输入规模、进入哪些子问题、合并新增了什么信息，不能只写最终答案。

记忆钩子：先写“分成什么、递归返回什么、怎样合并”，再列递推式；只会套主定理而说不清合并，说明算法还没有真正掌握。

八、实现代价、退化条件与替代方案

实现边界是：子问题大量重叠时应缓存或改动态规划；递归深度和合并空间也要计入。除了渐进时间，还要把递归栈、辅助数组、输入是否被修改以及最坏输入考虑进去。

检查项	面试中要回答的内容
基本情况	规模 0 或 1 时如何直接返回
规模缩小	每次递归是否严格靠近基本情况
合并正确性	子解怎样推出原问题答案
资源代价	递归深度、辅助结构与数据复制
退化保护	随机化、阈值切换、预排序或迭代改写

测试至少覆盖最小规模、奇偶长度、全部相等、严格有序/逆序、极端偏斜划分和会触发最大计数或溢出的数据。若存在更直接的线性算法、堆算法或动态规划，还要说明分治方案的教学价值与工程取舍。

九、常见误区与追问

误区：把问题递归拆开就叫分治。 还需要可解的基本情况与正确、可控的合并过程。
误区：分治子问题必须完全独立。 多数经典分治要求不重叠；若重叠严重会重复计算。
误区：主定理可以分析所有递归。 它只覆盖特定形式且有正则条件。
追问：分、治、合分别是什么？ 划分输入、递归解同构子问题、由子解构造原解。
追问：二分查找为何常称减治？ 每轮只进入一个子问题，而标准分治通常求解多个子问题。
追问：怎样证明分治正确？ 用归纳法证明基本情况，再证明子解正确能推出合并结果正确。

十、加强记忆

分治 = 分（拆成同类小问题）→ 治（递归解每个，到递归基直接返回）→ 合（子解拼成原解）。能用的前提是子问题同构、独立、可合并、有边界。它和动态规划的分界线是「子问题是否重叠」——独立用分治，重叠用 DP；只进一个子问题、无需合并的（二分、快速幂）严格叫「减治」。复杂度靠递归式 T(n)=aT(n/b)+f(n) + 主定理求解。

简化版

详细版