文档介绍：1
第2讲分治与递归策略
分治算法的基本思想
递归概念
典型分治算法举例
2
算法总体思想
将一个难以直接解决的规模较大的问题分解为若干个规模较小的子问题，并各个击破，分而治之。
，也可以是
公式法
上述方程描述了如下算法的运行时间：将一个规模为n的问题划分为a个规模为n/b的子问题，其中a和b为正常数。分别递归地解决a个子问题，解每个子问题所需时间为T(n/b)。划分原问题和合并子问题的解所需要的时间由f(n)决定
17
定理：上述递归方程含有三种情形的渐进界：
（1）对于某个常数 如果
则
（2）如果 则
（3）对某个常数 如果
且对某个常数 c <1 以及任意足够大的n,
有af(n/b)≤cf(n),则
18
定理含义
将f(n)与 进行比较，
当 较大时，
相等时
当 较小时，
结论：可以通过尽量减少子问题的个数或者减少f(n)的数量级来增强分治算法的有效性。
从定理中可以看出，公式法只要记住三种情形，
就可以很容易地确定许多递归方程的解。
19
例1：T(n)=9T(n/3)+n
由上式可知，a = 9，b = 3，f(n) = n,
且
又因为对于 有
满足定理（1），因此，
20
例2：T(n) = T(2n/3)+1
由上式可知a=1, b=3/2, f(n)=1，
且
又因为
满足定理（2），因此
21
递归概念
分治算法
递归技术
直接或间接地调用自身的算法称为递归算法。
在定义函数时调用到函数自身称为递归函数。
分治算法递归技术
分治与递归像一对孪生兄弟
分治算法的特征：将较大规模的问题分解为若
干个较小规模的子问题，每个子问题的求解过
程与原问题一样，并利用自底向上的求解策略
得到最终的解。
22
递归应用举例1: Fibonacci数列
边界条件
递归方程
边界条件与递归方程是递归函数的二要素。
无穷2阶数列1，1，2，3，5，8，13，21，34，
55，…，被称为Fibonacci数列。递归定义为：
23
A(1,0) = 2
A(0,m) = 1 m≥0
A(n,0) = n + 2 n≥2
A(n,m) = A(A(n-1,m),m-1) n,m≥1
递归应用举例2: Ackerman函数
24
m=2时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，
A(1,2)=A(A(0,2),1)=A(1,1)=2
可以得出A(n,2)= 2n 。
m=3时，类似的可以推出
A(1,0) = 2
A(0,m) = 1 m≥0
A(n,0) = n + 2 n≥2
A(n,m) = A(A(n-1,m),m-1) n,m≥1
Ackerman函数的特征：A(n，m)的自变量m的每一个值都定义了一个单变量函数。
m=0时，A(n,0)=n+2
m=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，
A(1,1)=2 可以得出A(n,1)=2*n
25
递归应用举例3: 排列问题
求解n个元素{r1,r2,…,rn}的全排列。
n个元素的全排列有n!种可能。
解题基本方法：
（1）固定位置放元素
（2）固定元素找位置
26
假设R={r1,r2,…,rn}是待排列的n个元素，Ri=R-{ri}。
假设集合Ri中元素的全排列记为perm(Ri)。
(ri)perm(Ri)表示在全排列perm(Ri)的每一个排列的第一
个位置加前缀ri得到的排列。
当n=1时，perm(R)=(r)
其中r是集合R中唯一的元素；
当n>1时，perm(R)的全排列为：
(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)
方法1：固定位置找元素
27
递归公式
28
29
将每个元素交换
到固定位置上，
并求解其余位置
元素的全排列。
举例，0~3共4个数值的全排列
思路？
30
假设: 要求P[m] 、P[m+1] 、… P[n]的全排列:
值得注意的是，将P[m]和某个