《算法导论》-- 分治策略

1. 步骤：

• 分解：将问题划分为一些子问题，子问题的形式和原问题一样，只是规模更小；
• 解决：递归的求解出子问题，如果子问题规模足够小，则停止递归，直接求解；
• 合并: 将子问题的解组合成原问题的解；

2. 递归式

• 代入法：我们猜测一个界，然后用数学归纳法证明这个界是正确的
  Ex:
  T(n) = 4T(n/2) + n
  --Guess: T(n) = O(n²)
  --Assume :T(k)<=ck² for k <n
  --T(n) = 4T(n/2) + n<=4c(n/2)²+n = cn²+n

--Guess: T(n) = O(n²)
--Assume :T(k)<=c1k²-c2k for k <n
--T(n) = 4T(n/2) + n<=4c1(n/2)²-c2(n/2)+n=c1n²+(1-2c2)n=c1n²-c2n-(-1+c2)n need (-1+c2)>0则有c2>1
and T(1) <= c1-c2 so c1 > c2

• 递归树法： 将递归式转换为一棵树，其结点表示不同层次的递归产生的代价，然后采用边界和技术来解递归式
  Ex: T(n)=T(n/4)+T(n/2)+n²
  递归树展开：

  
  image.png
  image.png
  

  叶节点（即最后一层节点）数小于n，这个很容易理解，完全二叉树的叶节点是n，这棵树的递归速度更快，每一层的节点更少。

  
  image.png

这是个几何级数求和，即 1+5/16n²+25/256n²+...(5/16)(k次方)*n²
由 1+1/2+1/4...+1/n(k次方) <2得 上式<2n²。

• 主方法：可求解形如下面公式的递归式的界：
  T(n) = aT(n/b) + f(n)
  其中 a>= 1,b>1,f(n)是一个给定的函数。这种形式的递归式很常见，它刻画了这样一个分治算法：生成a个子问题，每个子问题的规模是原问题的规模的1/b，分解和合并步骤共花费的时间为f(n)。

有三种情况：

image.png