分治策略-算法设计思想.md

算法设计思想

• 将原问题归结为规模为n-1的2个子问题；

• 继续归约，将原问题归结为规模为n-2的4个子问题。继续…，当子问题规模为1时，归约过程截止。

• 从规模1到n-1，陆续组合两个子问题的解。直到规模为n。

• 分析方法：递推方程。

一般性描述

分治算法 Divide-and-Conquer(P)

if |P|<=c then S(P)
divide P into P1,P2,...,Pk
for i ← 1 to k
    yi ← Divide-and-Conquer(Pi)
Return Merge(y1, y2, ..., yk)

设计要点

• 原问题可以划分或者归约为规模较小的子问题

  子问题与原问题具有相同的性质

  子问题的求解彼此独立

  划分时子问题的规模尽可能均衡

• 子问题规模足够小时可以直接求解

• 子问题的解综合可以得到原来的解

• 算法实现：递归或者迭代

分治算法时间分析

时间复杂度函数的递推方程：

$W(n)=W(|P_1|)+W(|P_1|)+...+W(|P_1|)+f(n) \\ W(c)=C$

• $P_1, P_2, ..., P_k$为划分后产生的子问题

• $f(n)$为划分子问题以及将子问题的解综合得到原问题解的总工作量

• 规模为$c$的最小子问题的工作量为$C$

两种常见的递推方程

$f(n)=\sum_{i=1}^{k}a_if(n-i)+g(n) \newline f(n)=af(\frac{n}{b})+d(n)$

• Hanoi塔，$W(n)=2W(n-1)+1$

• 二分检索，$W(n)=W(n/2)+1$

• 归并排序，$W(n)=2W(n/2)+n-1$

对于方程1$f(n)=\sum_{i=1}^{k}a_if(n-i)+g(n)$求解方法有迭代法、递归树；对于方程2$f(n)=af(\frac{n}{b})+d(n)$有迭代法、换元法、递归树、主定理。

方程2

方程 $T(n)=aT(n/b)+d(n)$

$d(n)$为常数时，

$T(n) = \begin{cases} \Omicron(n^{\log_ba}) &{a \neq 1} \\ \Omicron(\log {n}) &{a = 1} \end{cases}$

$d(n)=cn$时，

$T(n) = \begin{cases} \Omicron(n) &{a < b} \\ \Omicron(n \log {n}) &{a = b} \\ \Omicron(n^{\log_ba}) &{a > b} \end{cases}$