分治法是一种常用的算法设计技巧，二分法就是其最常见的特例。所谓分治，分而治之也：
- 分（divide）：递归解决较小的问题
- 治（conquer）：从子问题的解构建原问题的解
一般来说，至少含有两个递归的程序才叫做分治法，只有一个递归的程序是不算的。下面来总结下分治法的算法复杂度问题，摘自《数据结构与算法分析——C语言描述》一书。
假设每次递归均可把原问题分解为$b$个规模一样的子问题，并需要求解其中的$a$个问题，将这$b$个子问题的解合并起来所需的算法复杂度为$O(N^k)$，即：
$$T(N)=aT(N/b)+\Theta (N^k)$$
此方程的解为：
$$T(N)=
\begin{cases}
O(N^{\log_b a}) & a>b^k\\
O(N^k \log N) & a=b^k\\
O(N^k) & a<b^k
\end{cases}$$
其中$a \geqslant 1, b > 1$
这个公式的实质是分和治的过程在争夺主导地位。大部分情况下$a=b$，此时上式可以进一步简化：
$$T(N)=
\begin{cases}
O(N^k) & k>1\\
O(N \log N) & k=1\\
O(N) & k<1
\end{cases}$$
一般也不存在 $k < 1$ 的情况，故我们可以得到一个最常用的结论：
若合并复杂度为 $O(N)$, 则整个分治法的复杂度为 $O(N \log N)$ ; 若合并复杂度为 $O(N^k), k>1$ , 则整个分治法的复杂度就是合并复杂度。且无论将问题分为几个子问题求解，其算法复杂度相同。