算法-递归、分治

策略

Posted by MetaNetworks on October 15, 2019
本页面总访问量

分治

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

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}}}$(共n2)

排列问题

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)$
\[\left\{ \begin{array}{lr} M(n)=2M(n-1)+1 & n>1\\ M(1)=1&n=1 \end{array} \right.\]