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

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

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

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

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

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

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

设计一个递归算法生成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

将正整数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，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。 9

前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。 递归的例子 例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

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

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

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

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

分治法的基本步骤： 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

分治法的复杂性分析 通过迭代法求得方程的解： 一个分治法将规模为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

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

分治法的例子 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

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). 31415962 ×27182818 251327696 62831924 219911734 853974377340916 12 ×23 6 3 4 2 276 19

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102+64. Let m= n/2. Then XY = (10ma+b)(10mc+d) =102mac+10m(bc+ad)+bd 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 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

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

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

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

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

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

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

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

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

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

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

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

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) +23+22+2 = … = 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

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

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

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

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

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

谢谢！ Q & A 作业： 28.2-1 28.2-6 2018/12/9 39