分治法的思想,将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后再合并这些子问题的解来建立原问题的解。
分治模式在每层递归时的三个步骤:
分解步骤将问题划分为一些子问题,子问题的形式与原问题一样,只是规模更小。
解决步骤递归的求解子问题,如果子问题的规模足够小,则停止递归直接求解。
合并步骤将子问题的解组合成原问题的解。
分析分治算法
应用
归并排序
最大子数组问题
矩阵乘法的 Strassen 算法
Strassen 算法的运行时间的递归式为:
$T(n)=7T(n/2)+Θ(n^2)$
这里 a=7,b=2,$f(n)=Θ(n^2)$,即$n^{log_ba}=n^{log_27}$。存在ε=0.8有$f(n)=O(n^{lg7-ε})$。符合主定理的情况1,则$T(n)=Θ(n^{lg7})$。
最近点对算法
最近点对算法的递归式为:
$T(n)=2T(n/2)+O(n)$
这里 a=2,b=2,$f(n)=O(n)$,即$n^{log_ba}=n^{log_22}=n$。符合主定理的情况2,则$T(n)=O(nlgn)$。