分治
- 将大问题分解成一些规模较小的相同子问题(分而治之)
eg：排列
n个元素解：一分为二，分为两个元素的小单位进行排序
1.将规模为
n的划分为两个$\frac{n}{2}$规模的问题（如果还大则继续划分）2.将这些问题递归求解
条件
对于函数f(n)有基本部分和递归部分
- 基本部分
- 对于n的一个或多个值，
f(n)必须是直接定义的，也就是非递归的
- 对于n的一个或多个值，
- 递归部分
- 右侧所出现的所有
f的参数都必须比n小（如f(n)=f(n-1)...）
- 右侧所出现的所有
例子-1：
\(f(n)= \left\{
\begin{array}{lr}
1 &,n=0\\
n \times f(n-1)&,n>0
\end{array}
\right.\)
f(n)=1为非递归的，而n>0时参数比n小，则可以分治
例子-2(Ackerman函数)：
\(\left\{
\begin{array}{lr}
A(1,0) =& 2\\
A(0,m) =& 1\\
A(n,0) =& n+2\\
A(n,m) =& A(~A(n-1,m)~,~m-1~)
\end{array}
\right.\)
反向替换法算得复杂度=$2 \times n$
数学归纳法
eg: $A(n,1)=A(n-1,1)+2$
当$n=1$的时候，$A(1,1)$等于$2\times 1$
假设$A(n-1,1)=2\times (n-1)$
所以 \(\begin{array} ~A(n,1) &= A(n-1,1)+2\\ &=2 \times (n-1) + 2\\ &=2n \end{array}\) 当n=2，3，4…时，函数爆炸
$A(n,2) = 2^n,~~~~A(n,3)=2^{2^{2^{…^2}}}$(共n个2)
排列问题
1
2
3
4
5
6
7
8
9
10
11
Perm(A,k,m):
if k==m :
for x in A:
print(x)
else:
i = k
while i<=m:
A[k],A[i]=A[i],A[k]
Perm(A,k+1,m)
A[k],A[i]=A[i],A[k]
i = i + 1
- 正整数的划分
eg：5的划分数
- 5
- 4+1
- 3+2
- 3+1+1
- 2+2+1
- 2+1+1+1
- 1+1+1+1+1
思想：求5的划分数，先求4的划分，用数学归纳法推测
$q(n,m)$递归公式：
-
$n \ge 1$: $q(n,1)=1,~n=1+1+…+1.$
- $m>n$: $q(n,m) = q(n,n),q(1,m)=1$
- $m=n:~q(n,m)=1+q(n,n-1)$,正整数$n$的划分由$n_1=n$的划分和$n_1 \le n-1$的划分组成
- $n>m>1~:q(n,m)=q(n,m-1)+q(n-m,m)$;正整数$n$的最大加数$n_1$不大于m的划分由$n_1=m$的划分和$n_1 \le m-1$的划分组成
所以： \(q(n,m)=\left\{ \begin{array}{lr} 1 & n=1~or~m=1\\ q(n,n)& n<m\\ 1+q(n,n-1)&n=m\\ q(n,m-1)+q(n-m,m)&n>m>1 \end{array} \right.\) eg2:汉诺塔
- 选择盘子的数量$n$作为输入规模度量
- 选择盘子的移动作为算法的基本操作
- 移动次数为$M(n)$
