分治法也称为分解法、分治策略等。分治法算法思想如下：
(1) 将一个问题划分为同一类型的若干子问题，子问题最好规模相同。
(2) 对这些子问题求解（一般使用递归方法，但在问题规模足够小时，有时也会利用另一个算法）。
(3) 有必要的话，合并这些子问题的解，以得到原始问题的答案。
当子问题足够大时，需要递归求解时，我们称之为递归情况（Recursive Case）。当子问题变得足够小，不再需要递归时，表示递归已经“触底”，进入了基本情况（Base Case）。
以将一个问题划分为两个较小子问题为例，分治法的流程如下图所示：
递归式与分治方法紧密相关。因为使用递归式可以很自然地刻画分治算法的运行时间。一个递归式（Recurrence）就是一个等式或不等式，它通过更小的输入上的函数值来描述一个函数。如使用递归式表示归并排序(Merge Sort)的最坏运行时间
T
(
n
)
T(n)
T(n)：
T
(
n
)
=
O
(
1
)
(
n
=
1
)
T(n) = O(1) (n=1)
T(n)=O(1)(n=1)
T
(
n
)
=
2
T
(
n
/
2
)
+
O
(
n
)
(
n
>
1
)
T(n) = 2T(n/2) + O(n) (n>1)
T(n)=2T(n/2)+O(n)(n>1)
其中
O
(
1
)
O(1)
O(1)表示在常数级别求解问题。
《算法导论》给出三种求解递归式方法，即得出算法的“O”的渐近界的方法。他们是：(1) 代入法：猜测一个界，然后用数学归纳法证明这个界是正确的；(2) 递归树法：将递归式转换为一棵树，其其结点表示不同层次的递归调用产生的代价。然后采用边界和技术来求解递归式；(3) 主方法：可求解公式的递归式的界。
代入法也称代换法。代入法先猜测界的形式，然后使用数学归纳法证明这个界是正确的。本质上是数学归纳法在递归式求解的应用。实现步骤如下：
(1) 根据经验（如对比、类比、分类等等）等方式，猜测解的形式；
(2) 用数学归纳法求出解中的常数，并证明解是正确的。
之所以将其称为代入法，是因为需要将猜测的解代入函数。注意，不存在通用的方法来猜测递归式的正确解，猜测解要靠经验，偶尔还需要创造力。但是，有一些启发式方法帮助成为好的猜测者。如将当前问题和之前处理过的问题做类比、对比；先证明较宽松的上界和下界，然后缩写不确定的范围。
可以使用递归树表示递归式。在递归树中，每一个结点表示一个单一子问题的代价，子问题对应某次递归函数调用。我们将树中每层中的代价求和，得到每层代价，然后将所有层的代价求和，得到所有层次的递归调用总代价。
递归树最适合用来生成好的猜测，然后可用代入法来验证猜测是否正确。当使用递归树来生成好的猜测时，常常要忍受一点儿“不精确”，因为关注的是如何寻找解的一个上界。使用递归树生成好的猜测的步骤如下：
(1) 分析问题，得出递归式
(2) 基于递归式创建递归树
(3) 计算递归树的代价
(4) 对代价进行“不精确处理”，推导出猜测
主方法仅适用于分治法的递归式。主方法依赖主定理。在介绍主方法前，先介绍下主定理。假设我们有递推关系式：
T
(
n
)
=
a
T
(
n
/
b
)
+
f
(
n
)
T(n) = aT(n/b) + f(n)
T(n)=aT(n/b)+f(n)
其中，
n
n
n为问题的规模、
a
a
a为递推下子问题的数量，
n
/
b
n/b
n/b为每个子问题的规模，
f
(
n
)
f(n)
f(n)为递推后做的额外工作。
(1) 若存在常量
ϵ
>
0
\epsilon>0
ϵ>0，使得
f
(
n
)
=
O
(
n
l
o
g
b
(
a
)
−
ϵ
)
f(n) = O(n^{log_b^{(a)-\epsilon}})
f(n)=O(nlogb(a)−ϵ)，则
T
(
n
)
=
θ
(
n
l
o
g
b
a
)
T(n) = θ(n^{log_b^a})
T(n)=θ(nlogba)。
(2) 若存在常量
k
>
0
k>0
k>0，使得
f
(
n
)
=
θ
(
n
l
o
g
b
a
l
o
g
k
n
)
f(n)= θ(n{log_b^alog^kn})
f(n)=θ(nlogbalogkn)，则
T
(
n
)
=
θ
(
n
l
o
g
b
a
l
o
g
k
+
1
n
)
T(n)= θ(n{log_b^alog^{k+1}n})
T(n)=θ(nlogbalogk+1n)。
(3) 若存在常数
ϵ
>
0
\epsilon>0
ϵ>0，有
f
(
n
)
=
Ω
(
n
l
o
g
b
(
a
)
+
ϵ
)
f(n)=Ω(n{log_b^{(a) + \epsilon}})
f(n)=Ω(nlogb(a)+ϵ)，同时存在常数c<1，以及充分大的n满足
a
f
(
n
/
b
)
≤
c
f
(
n
)
af(n/b)≤cf(n)
af(n/b)≤cf(n)，那么
T
(
n
)
=
θ
(
f
(
n
)
)
T(n)=θ(f(n))
T(n)=θ(f(n))。
主定理的证明可以参考《算法导论》证明主定理一节。
在使用主定理前，先理解下其含义。首先将函数
f
(
n
)
f(n)
f(n)与函数
n
l
o
g
b
a
n{log_b^a}
nlogba进行比较。如果函数
f
(
n
)
f(n)
f(n)小于函数
n
l
o
g
b
a
n{log_b^a}
nlogba，则
T
(
n
)
=
θ
(
n
l
o
g
b
a
)
T(n) = θ(n^{log_b^a})
T(n)=θ(nlogba)。注意，这里是多项式意义上的小于。如果函数
f
(
n
)
f(n)
f(n)大于函数
n
l
o
g
b
a
n{log_b^a}
nlogba，则
T
(
n
)
=
θ
(
f
(
n
)
)
T(n)=θ(f(n))
T(n)=θ(f(n))。注意，这里同样是多项式意义上的大于。
注意，这三种情况并未覆盖
f
(
n
)
f(n)
f(n)的所有可能性。情况1和情况2之间有一定间隙，
f
(
n
)
f(n)
f(n)可能小于
n
l
o
g
b
a
n{log_b^a}
nlogba，但不是多项式意义上的小于。类似的，情况2和情况3之间也有一定间隙，
f
(
n
)
f(n)
f(n)可能大于
n
l
o
g
b
a
n{log_b^a}
nlogba，但不是多项式意义上的大于。如果
f
(
n
)
f(n)
f(n)落在上述两个间隙中，就不能使用主方法来求解递归式。
接下来介绍如何使用主方法。使用主方法很简单，只需要确定主定理哪种情况成立，即可得到解。具体步骤如下：
(1) 根据递推式获得a, b,
f
(
n
)
f(n)
f(n)的值;
(2) 计算
n
l
o
g
b
a
n{log_b^a}
nlogba;
(3) 基于
n
l
o
g
b
a
n{log_b^a}
nlogba表示
f
(
n
)
f(n)
f(n)，并明确ε，进而明确对应的情况（考虑间隙问题）
(4) 获取代价
接下来将从实践出发，在实际场景中使用分治算法。
归并排序，默认指二路归并排序。归并排序是使用分治法实现的排序之一。假设初始序列含有n个元素，则可看成n个有序的子序列，每个子序列的长度是1。然后将前后相邻的两个有序序列归并为一个有序序列。这与分治法**将一个问题划分为同一类型的若干子问题，对这些子问题求解，合并这些子问题的解的思路是一致的。更多相关介绍可以参考归并排序一文。
和归并排序一样，快速排序也是基于分治技术实现的算法。与归并排序按照元素在列表中的位置进行划分不同，快速排序是按照元素的值进行划分。快速排序的基本思想是，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列。更多相关介绍可以参考快速排序一文。
因为二叉树可以划分为同样类型的两个更小的组成部分——左子树和右子树，所以许多关于二叉树的问题都可以应用分治法来解决。二叉树是由三个基本单元组成：根结点、左子树和右子树。因此，若能依次遍历这三部分，就能遍历整个二叉树。更多相关介绍可以参考二叉树一文。
《算法导论》 第三版 Tomas H. Cormen etc. 殷建平 等译 第四章 分治策略
《算法设计与分析基础》第三版 Anany Levitin 著 潘彦 译 第五章 分治法
https://blog.csdn.net/u010013164/article/details/38819959 [算法导论] 递归式求解的三种方法
https://leetcode-cn.com/ leetcode
