算法导论 第4章 分治策略(1)
算法导论 第4章 分治策略(1)
分治策略 的三个步骤:
- 分解为若干子问题,子问题形式与原问题相同,但规模更小
- 递归地解决子问题,若子问题规模足够小则停止递归,直接求解
- 合并为原问题的解式
足够大需要递归求解的子问题称为 递归情况,不再需要递归的足够小的子问题称为 基本情况。
求解递归式,即得到算法的Θ或O渐近界的方法的方法:
- 代入法:猜测一个界,用数学归纳法证明
- 递归树法:将递归式转换为一棵树,节点表示递归调用产生的代价,然后用边界和技术来求解
- 主方法:用于解形如
的递归式
最大子数组问题
考虑购买股票的问题,希望在股票价格变化值的序列中找到最优购买和出售时机。
若使用暴力求解的方法,尝试每对可能的购买和出售时间组合,则运行时间为Ω(n2)。
将数据转变为每日价格相对于前一天的价格差,则问题转化为寻找数组A的和最大的非空连续子数组,即 最大子数组:
使用分治策略求解该问题,假设数组范围为A[low…high],*位置mid,则最大子数组必然位于三种情况之一:
- 完全处于子数组A[low…mid]中
- 完全处于子数组A[mid+1…high]中
- 跨越中点
即最大子数组为三种情况的所有子数组中和最大者。
跨越中点的情况比较容易,只需找到形如A[i…mid]和A[mid+1…j]的最大子数组并合并:
该方法花费Θ(n)时间。
由此即可设计出求解最大子数组问题的分治算法:
建立递归式来描述该算法运行时间:
使用主方法可求出其解为T(n)=Θ(nlgn),优于暴力求解的方法。
矩阵乘法的Strassen算法
考虑矩阵乘法问题,即:
常规计算方法:
该方法花费Θ(n3)时间。
使用分治方法计算矩阵乘法C=A·B,假定三个矩阵都是nxn,n为2的幂,将每个矩阵分解为4个n/2xn/2的子矩阵,于是矩阵乘法改写为:
直接进行递归分治算法:
其中矩阵分解时使用下标计算,花费Θ(1)时间,8次递归调用花费8T(n/2)时间,4次矩阵加法花费Θ(n2)时间,所以总的运行时间为:
Strassen方法在此基础上减少了一次矩阵乘法。其步骤如下:
- 将矩阵A、B、C分解为n/2xn/2的子矩阵,花费时间Θ(1)
- 创建10个n/2xn/2的矩阵S1…S10,每个矩阵保存步骤1中创建的两个子矩阵的和或差,花费时间Θ(n2)
- 用子矩阵和10个矩阵递归的计算7个矩阵积P1…P7,每个P矩阵都是n/2xn/2的。
- 通过P矩阵进行加减运算得到C矩阵的4个子矩阵,花费时间Θ(n2)
其中步骤2中创建的矩阵:
步骤3中的7次矩阵乘法:
步骤4中的矩阵加减法:
该算法运行时间:
由主方法可求得T(n)=Θ(nlg7)。