算法-递归、分治

分治

• 将大问题分解成一些规模较小的相同子问题(分而治之)

eg：排列n个元素

解：一分为二，分为两个元素的小单位进行排序

1.将规模为n的划分为两个$\frac{n}{2}$规模的问题（如果还大则继续划分）

2.将这些问题递归求解

条件

对于函数f(n)有基本部分和递归部分

• 基本部分
  • 对于n的一个或多个值，f(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)$

• Previous
  Linux-(信号量)银行-客人问题
• Next
  计算机网络-下一代互联网