目录
- 零、主定理
- 零-零、利用数学方法求解递归式
- 一、归并排序
*二、最大子数组问题
2.1 问题描述
2.2 使用分治策略求解
2.3 分治法的分析 - 三、矩阵乘法的Strassen算法
3.1 普通矩阵乘法
3.2 一个简答的分治算法
3.3 Strassen方法
在分治策略中，递归地求解一个问题，在每层递归中应用如下三个步骤：
1）分解：将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小
2）解决：递归地求解出子问题。如果子问题的规模足够小，则停止递归，直接求解。
3）合并：将子问题的解组合成原问题的解
分治有两种情况：
1）当子问题足够大，需要递归求解时，称之为递归情况
2）当子问题变得足够小，不再需要递归时，进入基本情况
零、主定理
主定理的三种情况分别对应以下三种情况：
1）树的总代价由叶节点的代价决定
2）树的总代价均匀分布在树的所有层次上
3）树的总代价由根节点的代价决定
主定理的证明：（需要用到下面两个引理）
引理4.2：
引理4.2的证明：
引理4.3：
4.3的证明：
主定理的应用：
几个递归公式的解：
1）T (n) = T (αn) + T ((1 − α)n) + n 的解为：T (n) = Θ(n lg n)
可以用代入法验证
2）T (n) = T (n − 1) + n的解为：T (n) = Θ(n²)
3）T (n) = T (√n) + 1 的解为：T(n) = Θ(lglgn)
4）T (n) = T (n/2) + T (n/4) + T (n/8) + n的解为：T(n) = Θ(n)
可以用代入法验证
5）T (n) = T (n − 1) + lg n的解为：T (n) = Θ(n lg n)
6）T (n) = T (n − 1) + 1/n的结尾：T(n) = Θ(lgn)
零-零、利用数学方法求解递归式
一、归并排序
二、最大子数组问题
2.1 问题描述
股票的买入卖出，使得收益最大
暴力求解方法：尝试每队可能的组合，共有n(n - 1) /2种，运行时间为Ω(n²)
问题转换：不从每日价格的角度去看待输入，二十考察每日价格变化，第i天的价格变化定义为第i天和第i-1天的价格差，将该数组定义为A。那么问题就转换为寻找A的和最大的非空连续子数组。称之为最大子数组。
只有当数组中包含负数时，最大子数组问题才有意义，否则整个数组和肯定是最大的。
2.2 使用分治策略求解
考虑求解子数组A[low..high]的最大子数组。
使用分治技术意味着将子数组划分为两个规模尽量相等的子数组，比如中央位置mid。A[low..high]的任何连续子数组A[i..j]所处的位置必然是一下三种情况之一：
这三种情况的求法：
A[low..mid]和A[mid+1..high]递归进行求解
跨mid的求解：找出A[i..mid]和A[mid+1..j]最大子数组，然后合并
求出这三个之后，然后选出其中的最大者，即为A[low..high]的最大子数组
2.3 分治法的分析
可得T(n) = Θ(nlgn)
三、矩阵乘法的Strassen算法
3.1 普通矩阵乘法
3.2 一个简答的分治算法
递归情况的总时间为分解时间、递归调用时间以及矩阵加法时间之和：
得到T(n) = Θ(n³)
3.3 Strassen方法
核心思想是令递归树少一点点，只递归进行7次而不是8次n/2 x n/2矩阵的乘法。
创建10个矩阵：
递归地计算7次矩阵乘法：
计算C的4个子矩阵：
运行时间的分析：
