分治策略

核心思路

问题求解 = 子问题求解 + 子问题解的组合
找到递归链的一个链节。

通过递归式求解时间复杂度

代入法：

猜想一个表达式，使用数学java归纳法证明
比如：对于递归式式 ，可以猜想表达式为

递归树法：

画出递归树，直到叶子的基础情形，将所有结点加起来。
这个方法可以帮助给出表达式的猜想

主方法：

分治算法常常得出如下形式的递归式：

将规模为 n 的问题分解为 a 个规模为 n/b 的子问题， 表示分解和合并子问题的代价。
主方法为：

1. 若 ，常数 ，则。
2. 若 ，则 。
3. 若 ，常数 ；且 ，常数 ， 足够大。那么。

例子分析：

• 归并排序和快速排序，其递归表达式均为：，主方法 求解为：。