0%

分治法

分治法的思想,将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后再合并这些子问题的解来建立原问题的解。

分治模式在每层递归时的三个步骤:

分解步骤将问题划分为一些子问题,子问题的形式与原问题一样,只是规模更小。

解决步骤递归的求解子问题,如果子问题的规模足够小,则停止递归直接求解。

合并步骤将子问题的解组合成原问题的解。

分析分治算法

应用

归并排序

最大子数组问题

矩阵乘法的 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)$。