主讲人： 吕敏 Email: {lvmin05@ustc.edu.cn } Spring 2012 ，USTC 算法基础 主讲人： 吕敏 Email: {lvmin05@ustc.edu.cn } Spring 2012 ，USTC.

Presentation on theme: "主讲人： 吕敏 Email: {lvmin05@ustc.edu.cn } Spring 2012 ，USTC 算法基础 主讲人： 吕敏 Email: {lvmin05@ustc.edu.cn } Spring 2012 ，USTC."— Presentation transcript:

1 主讲人： 吕敏 Email: {lvmin05@ustc.edu.cn } Spring 2012 ，USTC
算法基础 主讲人： 吕敏 } Spring ，USTC

2 第四讲 递归和分治策略 通过例子理解递归的概念； 掌握设计有效算法的分治策略； 通过几个范例学习分治策略设计技巧； Merge sort
第四讲 递归和分治策略 通过例子理解递归的概念； 掌握设计有效算法的分治策略； 通过几个范例学习分治策略设计技巧； Merge sort Multiplication of two numbers Multiplication of two matrices Finding Minimum and Maximum Majority problem (多数问题) 2

3 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
算法总体思想 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。 将要求解的较大规模的问题分割成k个更小规模的子问题。 T(n) = n T(n/2) T(n/2) T(n/2) T(n/2) 3

4 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
算法总体思想 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。 T(n) = n n/2 T(n/4) n/2 T(n/4) n/2 T(n/4) n/2 T(n/4) 4

5 T(n) n = n/2 算法总体思想 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
分治法的设计思想是，将一个难以直接解决的大问题， 分割成一些规模较小的相同问题，以便各个击破， 分而治之。 5

6 直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。
递归的概念 直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。 分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。 下面来看几个实例。 6

7 边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。
递归的例子 例1 阶乘函数 阶乘函数可递归地定义为： 边界条件 递归方程 边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。 7

8 设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。
递归的例子 例2 排列问题 设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。 设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}。 集合X中元素的全排列记为perm(X)。 (ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下： 当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素； 当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。 8

9 将正整数n表示成一系列正整数之和：n=n1+n2+…+nk， 其中n1≥n2≥…≥nk≥1，k≥1。
递归的例子 例3 整数划分问题 将正整数n表示成一系列正整数之和：n=n1+n2+…+nk， 其中n1≥n2≥…≥nk≥1，k≥1。 正整数n的这种表示称为正整数n的划分。求正整数n的不 同划分个数。 例如正整数6有如下11种不同的划分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1， ； 2+2+2， ， ； 。 9

10 前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。
递归的例子 例3 整数划分问题 前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。 在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。 (1) q(n,1)=1,n1; 当最大加数n1不大于1时，任何正整数n只有一种划分形式， 即 (3) q(n,n)=1+q(n,n-1); 正整数n的划分由n1=n的划分和n1≤n-1的划分组成。 (2) q(n,m)=q(n,n),mn; 最大加数n1实际上不能大于n。因此，q(1,m)=1。 (4) q(n,m)=q(n,m-1)+q(n-m,m),n>m>1; 正整数n的最大加数n1不大于m的划分由n1=m的划分和 n1≤m-1 的划分组成。 10

11 递归的例子 例3 整数划分问题 。 正整数n的划分数p(n)=q(n,n)。 11

12 递归小结 优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。
缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 12

13 递归小结 解决方法：在递归算法中消除递归调用，使其转化为非递归算法。
1、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。 2、用递推来实现递归函数。 3、通过变换能将一些递归转化为尾递归，从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善，但其适用范围有限。 13

14 分治法的适用条件 分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决；
该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。 能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。 因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。 这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用 14

15 分治法的基本步骤： divide-and-conquer(P) {
if ( | P | <= n0) adhoc(P); //解决小规模的问题 divide P into smaller subinstances P1,P2,...,Pk；//分解问题 for (i=1,i<=k,i++) yi=divide-and-conquer(Pi); //递归的解各子问题 return merge(y1,...,yk); //将各子问题的解合并为原问题的解 } 人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。 15

16 分治法的复杂性分析 通过迭代法求得方程的解：
一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有： 通过迭代法求得方程的解： 注意：递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当mi≤n<mi+1时，T(mi)≤T(n)<T(mi+1)。 16

17 分治法例子 Examples: Merge sort Multiplication of two numbers
Multiplication of two matrices Finding Minimum and Maximum Majority problem (多数问题) 循环赛日程表 17

18 分治法的例子 1. 整数相乘问题。 X和Y是两个n位的十进制整数，分别表示为
1. 整数相乘问题。 X和Y是两个n位的十进制整数，分别表示为 X=xn-1xn-2...x0, Y=yn-1yn-2...y0，其中0 ≤ xi, yj ≤ 9 (i, j=0,1,…n-1) ，设计一个算法求X×Y，并分析其计算复杂度。说明：算法中“基本操作”约定为两个个位整数相乘xi×yj，以及两个整数相加。 2. 矩阵相乘问题。 A和B是两个n阶实方阵，表示为 ， 设计一个算法求A×B，并分析计算复杂度。 说明：算法中“基本操作”约定为两个实数相乘，或两个实数相加。 18

19 Exam1 Multiplication of two numbers（大整数的乘法）
two n-digit numbers X and Y, Complexity(X × Y) = ? Naive (原始的) pencil-and-paper algorithm Complexity analysis: n2 multiplications and at most n2-1 additions (加法). So, T(n)=O(n2). × 12 ×23 6 3 4 2 276 19

20 Exam1 Multiplication of two numbers（大整数的乘法）
two n-digit numbers X and Y, Complexity(X × Y) = ? Divide and Conquer algorithm Let X = a b Y = c d where a, b, c and d are n/2 digit numbers, e.g. 1364=13 Let m= n/2. Then XY = (10ma+b)(10mc+d) =102mac+10m(bc+ad)+bd 20

21 Exam1 Multiplication of two numbers（大整数的乘法）
two n-digit numbers X and Y, Complexity(X × Y) = ? Divide and Conquer algorithm Let X = a b , Y = c d then XY = (10ma+b)(10mc+d) = 102mac+10m(bc+ad)+bd Multiply(X; Y; n): if n = 1 return XY else m = n/2 a = X/10m; b=X mod 10m c = Y/10m; d=Y mod 10m e = Multiply(a; c; m) f = Multiply(b; d; m) g = Multiply(b; c; m) h = Multiply(a; d; m) return 102me + 10m(g + h) + f Complexity analysis: T(1)=1, T(n)=4T(n/2)+O(n). Applying Master Theorem, we have T(n)= O(n2). 21

22 Exam1 Multiplication of two numbers（大整数的乘法）
two n-digit numbers X and Y, Complexity(X × Y) = ? Divide and Conquer (Karatsuba’s algorithm) Let X = a b , Y = c d then XY = (10ma+b)(10mc+d) = 102mac+10m(bc+ad)+bd Note that bc + ad = ac + bd  (a  b)(c  d). So, we have FastMultiply(X; Y; n): if n = 1 return XY else m = n/2 a = X/10m; b=X mod 10m c = Y/10m; d=Y mod 10m e = FastMultiply(a; c; m) f = FastMultiply(b; d; m) g = FastMultiply(ab; cd; m) return 102me + 10m(e + f  g ) + f Complexity analysis: T(1)=1, T(n)=3T(n/2)+O(n). Applying Master Theorem, we have 22

23 Exam1 Multiplication of two numbers（大整数的乘法）
更快的方法?? 如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。 最终的，这个思想导致了快速傅利叶变换(Fast Fourier Transform)的产生。该方法也可以看作是一个复杂的分治算法。 23

24 Exam2 Multiplication of two matrices（矩阵相乘）
two n×n matrices A and B, Complexity(C=A×B) = ? Standard method MATRIX-MULTIPLY(A, B) for i ← 1 to n for j ← 1 to n C[i, j] ← 0 for k ← 1 to n C[i, j]←C[i, j]+A[i, k]·B[k, j] return C Complexity: O(n3) multiplications and additions. T(n)= O(n3). 24

25 Exam2 Multiplication of two matrices（矩阵相乘）
two n×n matrices A and B, Complexity(C=A×B) = ? Divide and conquer An n×n matrix can be divided into four n/2×n/2 matrices, A = , B = , C = C11=A11B11+A12B21, C12=A11B12+A12B22 C21=A21B11+A22B21, C22=A21B12+A22B22 Complexity analysis: Totally, 8 multiplications (subproblems), and 4 additions (n/2×n/2×4). T(1)=1, T(n) = 8T( n/2 )+n2. Applying Master Theorem, we have T(n)= O(n3) (§28.2 ) 25

26 Exam2 Multiplication of two matrices(矩阵相乘)(§28.2)
two n×n matrices A and B, Complexity(C=A×B) = ? Divide and conquer (Strassen Algorithm) An n×n matrix can be divided into four n/2×n/2 matrices, A = , B = , C = Define P1 = (A11+A22)(B11+B22) P2 = (A11+A22)B11 P3 = A11 (B11B22) P4 = A22 (B11+B22) P5 = (A11+A12)B22 P6 = (A11+A21)(B11+B12) P7 = (A12 A22)(B21+B22) Then C11=P1+P4P5+P7, C12=P3+P5 C21=P2+P4, C22=P1+P3P2+P6 Complexity analysis: Totally, 7 multiplications, and 18 additions. T(1)=1, T(n) = 7T( n/2 )+ cn2. Applying Master Theorem, 26

27 Exam2 Multiplication of two matrices（矩阵相乘）
更快的方法?? Hopcroft和Kerr已经证明(1971)，计算2个２×２矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算2×2矩阵的7次乘法这样的方法了。或许应当研究３×３或５×５矩阵的更好算法。 在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376) 是否能找到O(n2)的算法？ 27

28 Exam4 Finding Minimum and Maximum（MaxMin）
Background Find the lightest and heaviest of n elements using a balance that allows you to compare the weight of 2 elements. （对于一个具有 n 个元素的数组，用一个天平，通过比较 2个元素的重量，求出最轻和最重的一个） Goal Minimize the number of comparisons. （正确找出需要的元素，最少的比较次数？） 28

29 Exam4 Finding Minimum and Maximum（MaxMin）
Max element Find element with max weight (重量) from w[0, n-1] Number of comparisons (比较次数) is n1. maxElement=0 for (int i = 1; i < n; i++) if (w[maxElement] < w[i]) maxElement = i; Obvious method（直接法） Find the max of n elements making n1 comparisons. Find the min of the remaining n1 elements making n2 comparisons. Total number of comparisons is 2n3. 29

30 Exam4 Finding Minimum and Maximum（MaxMin）
Divide and conquer Example Find the min and max of {3,5,6,2,4,9,3,1}. A = {3,5,6,2} and B = {4,9,3,1}. min(A) = 2, min(B) = 1. max(A) = 6, max(B) = 9. min{min(A),min(B)} = 1. max{max(A), max(B)} = 9. 选苹果；挑运动员；…… 30

31 Exam4 Finding Minimum and Maximum（MaxMin）
Divide and conquer Example Dividing Into Smaller Problems {8,2,6,3,9,1,7,5,4,2,8} {8,2,6,3,9} {1,7,5,4,2,8} {8,2} {6,3,9} {6} {3,9} {1,7,5} {4,2,8} {1} {7,5} {4} {2,8} 31

32 Exam4 Finding Minimum and Maximum（MaxMin）
Divide and conquer Example Solve Small Problems and Combine {2,8} {6,6} {3,9} {2,9} {1,1} {5,7} {1,7} {4,4} {1,8} {1,9} {8,2} {6} {3,9} {1} {7,5} {4} {2,8} 32

33 Exam4 Finding Minimum and Maximum（MaxMin）
Divide and conquer MaxMin(L) if length(L)=1 or 2, we use at most one comparison. else { split (分裂) L into lists L1 and L2, each of n/2 elements (min1, max1) = MaxMin(L1) (min2, max2) = MaxMin(L2) return (Min(min1, min2), Max(max1, max2)) } Complexity analysis (Number of Comparisons): T(1)=0, T(2)=1, T(n) = 2T(n/2)+2 = 4T(n/4)+22+2 = 23T(n/23) = … = 2k-1T(n/2k-1)+2k-1 +…+2 = 2k-1+2k-1 +…+2 = 2k-1+2k -2 = 3n/2 – 2 (there, assume n=2k ) 33

34 Exam4 Finding Minimum and Maximum（MaxMin）
Comparison between Obvious method (2n-3) and Divide-and-Conquer method (3n/2-2) Assume that one comparison takes one second. Time 2n3 3n/22 1 minute n=31 n=41 1 hour n=1801 n=2401 1 day n=43201 n=57601 34

35 Exam5 Majority Problem (多数问题)
Given an array A of n elements, only use “=” test to find the majority element (which appears more than n/2 times) in A. For example, given (2, 3, 2, 1, 3, 2, 2), then 2 is the majority element because 4>7/2. Trivial solution: counting (计数) is O(n2). Majority(A[1, n]) for(i = 1 to n) M = 1 for(j = 1 to n) if (i != j and A[i]==A[j]) M++ end if (M>n/2) return “A[i] is the majortiy” return “No majortity” 35

36 Exam5 Majority Problem (多数问题)
Divide and conquer Complexity analysis (Counting): T(n) = 2T(n/2)+O(n) = O(nlogn) Majority(A[1, n]) if n=1, then return A[1] else m1=Majority(A[1, n/2]) m2=Majority(A[n/2+1, n]) test if m1 or m2 is the majority for A[1, n] return majority or no majority. A=(2, 1, 3, 2, 1, 5, 4, 2, 5, 2) f[1] = 2 f[2] = 4 f[3] = 1 f[4] = 1 f[5] = 2 for(i=1 to n) ++frequency[ A[i] ] M = Max(frequency[ A[i] ] ) if (M > n/2) check( M = = frequency[ A[j] ] ) return “A[j] is the majority” However, there is a linear time algorithm for the problem. Moral (寓意) of the story? 36

37 Exam5 Majority Problem (多数问题)
Divide and conquer Majority(A[1, n]) if n=1, then return A[1] else m1=Majority(A[1, n/2]) m2=Majority(A[n/2+1, n]) test if m1 or m2 is the majority for A[1, n] return majority or no majority. Complexity analysis (Counting): T(n) = 2T(n/2)+O(n) = O(nlogn) However, there is a linear time algorithm for the problem. Moral (寓意) of the story: Divide and conquer may not always give you the best solution! 37

38 Exam6 循环赛日程表 设计一个满足以下要求的比赛日程表： (1)每个选手必须与其他n-1个选手各赛一次； (2)每个选手一天只能赛一次；
按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。 1 2 3 4 5 6 7 8 38

39 谢谢！ Q & A 作业： 2018/12/9 39