分治法1

基本步骤：

1. 将问题分解成若干个相同的小问题（可以有特殊处理）
2. 对每个小问题求解
3. 将小问题的解合并起来(可以有特殊处理)

示例

bit位为n的整数相乘

1. 常规算法，其复杂度为O(n2)
2. 现在将x,y表示成：
   
   x=x1∗2n/2+x0y=y1∗2n/2+y0
   
   x1,x0,y1,y0各自只有n/2个bit位。我们需要知道x1y1,x1y0+x0y1,x0∗y0，就可以求出xy的值。需要做四次运算，采用得到上面的值，所以复杂度没有降低，但是我们可以通过下面的方法将运算量从4次减到3次：
   
   1. 首先计算(x1+x0)∗(y1+y0)=x0y0+(x0y1+x1y0)+x1y1
   2. 计算x0y0
   3. 计算x1y1
      通过上面三步就可以得出我们想要的三组数据了，这样问题的复杂度变成了T(n)=3T(n/2)+cn,这个时候d<logba，所以问题的复杂度为O(nlog23)，这样就将问题的复杂度降低了。

规模为n的矩阵相乘

1. 其基本方法的复杂度为O(n3)。
2. 同理，我们也可以采用如整数相乘一样，采用分解与整合的方法来降低复杂度。
   
   上面的算法是一个启发式的算法，所以其简化没有严密性的推理。
   通过上面的方法我们就可以将复杂度从O(n3)降到O(nlog27)。