<分治策略>
分治策略三步骤：
- 分解：将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小。
- 解决：递归地求解出子问题，如果子问题地规模足够小，则停止递归，直接求解。
- 合并：将子问题地解组合成原问题地解。
- 递归情况：子问题足够大，需要递归求解。
- 基本情况：子问题足够小，不再需要递归时。
求解递归式的三种方法
- 代入法：猜测一个界，通过数学归纳法验证其正确性。
- 递归树法：将递归式转换为一棵树，其结点表示不同层次的递归调用产生的代价，采用边界和技术来求解递归式。
- 主方法(主推)
-
，其中
，
，
是一个给定的函数。
- 该问题生成a个子问题，每个子问题的规模是原问题规模的1/b，分解和合并步骤总共花费时间为
技术细节，一般忽略
- n值的奇偶
- 边界条件，即n很小时
4.1最大子数组问题
最大子数组：最大的非空连续子数组，寻找子数组A[low..high]，一般会出现以下三种情况：
- 完全位于子数组A[low.. mid]中，因此low≤i≤j≤mid
- 完全位于子数组A[mid+1..high]中，因此mid≤i≤j≤high
- 跨越了中点，因此low≤i≤mid≤j≤high
原方案一个个计算 ，分治策略中对于重复运算的可直接调用，减少运算时间。
获得运行时间递推式T(n)为，得解为
4.2 矩阵乘法的Strassen算法
使用下标计算，简单的分治算法得到的递推关系式为
花费时间为
Strassen算法
减少一次矩阵乘法带来的代价可能是额外几次×
矩阵的乘法。
- 将输入矩阵A、B和输出矩阵C分解为
×
。
- 创建10个n/2×n/2的矩阵S1,S2,……,S10，每个矩阵保存步骤1中创建的两个子矩阵的和或差。花费时间为
。
- 用步骤1中创建的子矩阵和步骤2中创建的10个矩阵，递归计算7个矩阵积P1，P2，…，P7。每个矩阵Pi都是
- 通过矩阵Pi的不同组合进行加减运算，计算出结果矩阵C的子矩阵
，
，
，
。花费时间为
4.3用代入法求解递归式
- 猜测解的形式（类似的证明递归式较松的上界和下界，然后缩小不确定的范围）。
- 用数学归纳法求出解中的常数，并证明解是正确的。
4.4用递归式方法求解递归式
每个结点表示一个单一子问题的代价，子问题对应某次递归函数调用。将树中每层中的代价求和，得到每层代价后将所有层的代价求和，得到所有层次的递归调用的总代价。
4.5用主方法求解递归式
，其中
，
，
是渐进正函数。
主定理
令，
是常数，是定义在非负整数上的递归式
其中将n/b解释为⌈n/b⌉ ⌊n/b⌋。那么T(n)有如下渐近界：
- 若对某个常数ε＞0有
，则
- 若
，则
- 若对某个常数ε＞0有
，且对某个常数
和所有足够大的n有
，则
。
Monge阵列
对一个m×n的实数阵列A，若对所有满足1≤i≤k≤m和1≤j≤l≤n的i，j，k和l有A[i, j]+ A[k, l] ≤A[i, l]+ A[k, j]，则称A是Monge阵列。即，无论何时选出Monge阵列的两行两列，对于交叉点上的4个元素，左上和右下两个元素之和总是小于等于坐下和右上元素之和。
更一般的
其中
求得递归式的解为
