第四章-递归和分治-算法设计与分析课件.ppt

1、1第四章第四章 递归和分治递归和分治 4.1 基于归纳的递归算法基于归纳的递归算法 4.2 分治法分治法 24.1 基于归纳的递归算法基于归纳的递归算法 一一 基于归纳的递归算法的思想方法基于归纳的递归算法的思想方法 二二 递归算法的例子递归算法的例子 三三 排列问题的递归算法排列问题的递归算法 四四 求数组主元素的递归算法求数组主元素的递归算法 五五 整数划分问题的递归算法整数划分问题的递归算法 3一一 归纳法的思想方法归纳法的思想方法解规模为解规模为 n 的问题的问题 P(n)：1.基础步：基础步：是问题是问题 P(1)的解的解2.归纳步：对所有的归纳步：对所有的 k，1 k n，若，若

2、是问题是问题 P(k)的的 解，则解，则 是问题是问题 P(k+1)的解，其中，的解，其中，是对是对 的某种运算或处理的某种运算或处理为求问题为求问题 P(n)的解的解 ，先求问题，先求问题 P(n 1)的解的解 ，再对，再对 进行进行 运算或处理，得到运算或处理，得到为求问题为求问题 P(n 1)的解的解 ，先求问题，先求问题 P(n 2)的解的解 再进行再进行 运算或处理，得到运算或处理，得到如此等等，不断地进行递归求解，直到如此等等，不断地进行递归求解，直到 P(1)的解的解 为止为止当得到当得到 P(1)的解之后，再回过头来，不断地把所得到的解的解之后，再回过头来，不断地把所得到的解进

3、行进行 p 运算或处理，直到得到运算或处理，直到得到 P(n)的解为止的解为止 ka)a(pk)a(pkka1ana-1na-1na)a(p-1nna-1na2-na)a(p2-n-1na1a4二二 递归算法的例子递归算法的例子1.计算阶乘函数计算阶乘函数 n!阶乘函数可归纳定义为阶乘函数可归纳定义为 递归算法如下：递归算法如下：1.int factorial(int n)2.3.if(n=0)4.return 1;5.else 6.return n*factorial(n-1);7.0!)1(01!nnnnn5二二 递归算法的例子递归算法的例子1.计算阶乘函数计算阶乘函数 n!算法的时间复杂

4、性可由如下递归方程确定：算法的时间复杂性可由如下递归方程确定：解此方程，有：解此方程，有：1)1()(0)0(nfnff)()(nnnf6二二 递归算法的例子递归算法的例子2.基于递归的插入排序基于递归的插入排序 对对 n 个元素的数组进行排序个元素的数组进行排序 1）基础步：当）基础步：当 n=1 时，数组只有一个元素，它已经是排时，数组只有一个元素，它已经是排 序的；序的；2）归纳步：如果前面）归纳步：如果前面 k-1 个元素已经按递增顺序排序，只个元素已经按递增顺序排序，只 要对第要对第 k 个元素逐一与前面个元素逐一与前面 k-1 个元素比较，把它插入个元素比较，把它插入 适当的位置，

5、即可完成适当的位置，即可完成 k 个元素的排序个元素的排序 7二二 递归算法的例子递归算法的例子2.基于递归的插入排序基于递归的插入排序 算法描述：算法描述：1.template 2.void insert_sort_rec(Type A,int n)3.4.int k;5.Type a;6.n=n 1;8二二 递归算法的例子递归算法的例子2.基于递归的插入排序基于递归的插入排序 算法描述：算法描述：7.if(n0)8.insert_sort_rec(A,n-1);9.a=An;10.k=n 1;11.while(k=0)&(Aka)12.Ak+1=Ak;13.k=k-1;14.15.Ak+1

6、=a;16.17.9二二 递归算法的例子递归算法的例子2.基于递归的插入排序基于递归的插入排序 算法的时间复杂性可由如下递归方程确定算法的时间复杂性可由如下递归方程确定 容易得到：容易得到：因此，算法的时间复杂性是因此，算法的时间复杂性是)1()1()(0)0(nnfnff)1(21)1()(111nniinfnini)(2nO10二二 递归算法的例子递归算法的例子3.整数羃的计算整数羃的计算 计算以计算以 x 为底的为底的 n 次羃，简单的方法是让次羃，简单的方法是让 x 乘以自身乘以自身 n 次。次。但效率低，需要但效率低，需要(n)个乘法。下面算法可以用个乘法。下面算法可以用(logn)

7、来实现它。来实现它。1.int power(int x,int n)2.3.int y;4.if(n=0)y=1;5.else 6.y=power(x,n/2);7.y=y*y;8.if(n%2=1)9.y=y*x;10.11.return y;12.11二二 递归算法的例子递归算法的例子3.整数羃的计算整数羃的计算 第第 7 行的乘法作为算法的基本操作，时间复杂性估计如下行的乘法作为算法的基本操作，时间复杂性估计如下 设设 ，把上式改写成，把上式改写成 有：有：1)2/()(1)1(nfnffkn2)2()(kfkg1)1()(1)0(kgkgg)log(1log1)()(nnkkgnf12

8、二二 递归算法的例子递归算法的例子4.多项式求值的递归算法多项式求值的递归算法 n 阶多项式：阶多项式：1）基础步：）基础步：n=0，有，有 ；2）归纳步：对任意的）归纳步：对任意的 k，1kn，如果前面，如果前面 k-1 步已计步已计 算出算出 ，则有：，则有：把把 存放于存放于 A0，存放于存放于 A1，如此等等，如此等等 0111)(axaxaxaxPnnnnn01321)(axaxxaxaxaxannnnnap01kpknkkapxp1na1na13二二 递归算法的例子递归算法的例子4.多项式求值的递归算法多项式求值的递归算法 1.float horner_pol(float x,fl

9、oat A,int n)2.3.float p;4.if(n=0)5.p=A0;6.else 7.p=horner_pol(x,A,n-1)*x+An;8.return p;9.14二二 递归算法的例子递归算法的例子4.多项式求值的递归算法多项式求值的递归算法 把第把第7行的乘法作为基本操作，算法的时间复杂性由如下的行的乘法作为基本操作，算法的时间复杂性由如下的 递归方程确定：递归方程确定：可得：可得：1)1()(0)0(nfnff)()(nnf15三三 排列问题的递归算法排列问题的递归算法 1.排列问题递归算法的思想方法排列问题递归算法的思想方法 2.排列问题递归算法的描述排列问题递归算法的

10、描述 3.排列问题递归算法的求解过程排列问题递归算法的求解过程 161.排列问题递归算法的思想方法排列问题递归算法的思想方法存放于数组存放于数组 A 的的 n 个元素，生成其排列的步骤：个元素，生成其排列的步骤：1）第一个元素不动，生成后面）第一个元素不动，生成后面 n 1 个元素的排列个元素的排列2）第一、第二个元素互换，生成后面）第一、第二个元素互换，生成后面 n 1 个元素的排列个元素的排列3）最后，第一个、第）最后，第一个、第 n 个元素互换，生成后面个元素互换，生成后面 n 1 个元个元 素的排列；素的排列；为生成后面为生成后面 n 1 个元素的排列，继续采取下面的步骤：个元素的排列

11、，继续采取下面的步骤：1）第二个元素不动，生成后面）第二个元素不动，生成后面 n 2 个元素的排列个元素的排列2）第二、第三个元素互换，生成后面）第二、第三个元素互换，生成后面 n 2 个元素的排列个元素的排列3）最后，第二个、第）最后，第二个、第 n 个元素互换，生成后面个元素互换，生成后面 n 2 个元个元 素的排列；素的排列；17排列问题递归算法的思想方法（续）排列问题递归算法的思想方法（续）当排列的前当排列的前 n 2 个元素确定后，为生成后面个元素确定后，为生成后面 2 个元素的排列，个元素的排列，可以：可以：1）第）第 n 1 个元素不动，生成后面个元素不动，生成后面 1 个元素的

12、排列，此时个元素的排列，此时 n 个元素已构成一个排列；个元素已构成一个排列；2）第）第 n-1、第、第 n 个元素互换，生成后面个元素互换，生成后面 1 个元素的排列，个元素的排列，此时，此时，n 个元素已构成一个排列；个元素已构成一个排列；令排列算法令排列算法 perm(A,k,n)表示生成数组后面表示生成数组后面 k 个元素的列。个元素的列。有：有：1）基础步：）基础步：k=1，只有一个元素，已构成一个排列；，只有一个元素，已构成一个排列；2）归纳步：对任意的）归纳步：对任意的 k，1 k n，为完成，为完成 perm(A,k,n)，逐一对第逐一对第 n k,与第与第 n k n 元素进

13、行互换，每互换一元素进行互换，每互换一 次，就执行一次次，就执行一次 perm(A,k-1,n)操作，产生一个排列操作，产生一个排列 182.排列问题递归算法的描述排列问题递归算法的描述 2.void perm(Type A,int k,int n)3.int i;5.if(k=1)6.for(i=0;in;i+)/已构成一个排列已构成一个排列,输出它输出它 7.cout A i;8.else 9.for(i=n-k;in;i+)/生成后续的一系列排列生成后续的一系列排列 10.swap(A i,A n-k);11.perm(A,k-1,n);12.swap(A i,A n-k);13.14.

14、15.193.排列问题递归算法的求解过程排列问题递归算法的求解过程 2.void perm(Type A,int k,int n)3.int i;5.if(k=1)6.for(i=0;in;i+)7.cout A i;8.else 9.for(i=n-k;in;i+)10.swap(A i,A n-k);11.perm(A,k-1,n);12.swap(A i,A n-k);13.14.15.ik 11n 33A 的的 内内 容容 123132i 1 2n k=1 k 2n 3A 的的 内内 容容 123 132 123i 0n k=0 k 3n 3A 的的 内内 容容 12320排列问题递归

15、算法的求解过程排列问题递归算法的求解过程（续（续 1）2.void perm(Type A,int k,int n)3.int i;5.if(k=1)6.for(i=0;in;i+)7.cout A i;8.else 9.for(i=n-k;in;i+)10.swap(A i,A n-k);11.perm(A,k-1,n);12.swap(A i,A n-k);13.14.15.ik 11n 33A 的的 内内 容容 213231i 1 2n k=0 k 2n 3A 的的 内内 容容 213 231 213i 1n k=0 k 3n 3A 的的 内内 容容 123 213 12321排列问题递

16、归算法的求解过程排列问题递归算法的求解过程（续（续 2）2.void perm(Type A,int k,int n)3.int i;5.if(k=1)6.for(i=0;in;i+)7.cout A i;8.else 9.for(i=n-k;in;i+)10.swap(A i,A n-k);11.perm(A,k-1,n);12.swap(A i,A n-k);13.14.15.ik 11n 33A 的的 内内 容容 321312i 1 2n k=0 k 2n 3A 的的 内内 容容 321 312 321i 2n k=0 k 3n 3A 的的 内内 容容 123 321 12322四四 求

17、数组主元素的递归算法求数组主元素的递归算法 1.求数组主元素递归算法的思想方法求数组主元素递归算法的思想方法 2.求数组主元素递归算法的描述求数组主元素递归算法的描述 3.时间复杂性估计时间复杂性估计 23 1.求数组主元素递归算法的思想方法求数组主元素递归算法的思想方法1）数组主元素：）数组主元素：A 是具有是具有 n 个元素的数组，个元素的数组，x 是是 A 中的一个元素，若中的一个元素，若 A 中有一半以上的元素与中有一半以上的元素与 x 相同，就称相同，就称 x 是数组的主元素。是数组的主元素。例：数组例：数组 A=1,3,2,3,3,4,3 中，中，元素元素 3 是该数组的主元素是该

18、数组的主元素 24 1.求数组主元素递归算法的思想方法求数组主元素递归算法的思想方法2）数组主元素性质：）数组主元素性质：移去数组中两个不同元素后，如果原来数组中有主元移去数组中两个不同元素后，如果原来数组中有主元 素，该主元素仍然是新数组的主元素。素，该主元素仍然是新数组的主元素。如果数组如果数组 2k 个元素中有个元素中有 k 个元素相同，那么，移去个元素相同，那么，移去 这这 2k 个元素后，如果原来数组中有主元素，该主元个元素后，如果原来数组中有主元素，该主元 素仍然是新数组的主元素。素仍然是新数组的主元素。对数组不断施加上述两种操作，最后将得到如下结果：对数组不断施加上述两种操作，最

19、后将得到如下结果：新数组只剩下一个元素：该元素可作为主元素的候新数组只剩下一个元素：该元素可作为主元素的候 选者。选者。新数组是若干个相同的元素：该元素可作为主元素新数组是若干个相同的元素：该元素可作为主元素 的候选者。的候选者。没剩余元素：原来数组没有主元素没剩余元素：原来数组没有主元素 25 1.求数组主元素递归算法的思想方法求数组主元素递归算法的思想方法3）思想方法：）思想方法：假定寻找主元素候选者的算法为假定寻找主元素候选者的算法为 dandidate(Type A,int n,int m)n：数组元素个数，：数组元素个数，m：数组前面被移去的元素个数，：数组前面被移去的元素个数，基础

20、步：基础步：n-m=0：没有主元素候选者：没有主元素候选者 n-m=1：Am 是主元素候选者，或者：是主元素候选者，或者：Am An-1 是同一元素：是同一元素：Am 是主元素候选者是主元素候选者 归纳步：归纳步：据性质据性质 1 移去移去 Am An+1，用，用 dandidate(A,n,m+2)寻找主元素候选者，或者：寻找主元素候选者，或者：据性质据性质2 移去移去 Am An+2k-1，k(n-m)/2，用，用 dandidate(A,n,m+2k)寻找主元素候选者。寻找主元素候选者。262.求数组主元素递归算法的描述求数组主元素递归算法的描述 2.BOLL dandidate(Typ

21、e A,Type&c,int n,int m)3.4.int j=m,count=1;5.c=Am;6.while(j0)7.j=j+1;8.if(Aj=c)count=count+1;9.else count=count 1;10.11.if(j=n-1&count0)return TRUE;12.else if(j=n-1&count=0)return FALSE;13.else return candidate(A,c,n,j+1);14.272.求数组主元素递归算法的描述求数组主元素递归算法的描述 2.BOLL majority(Type A,Type&m,int n)3.4.int

22、j,count=0,k=0;5.BOLL flag;6.flag=dandidate(A,m,n,0);7.if(flag)8.for(j=0;jn;j+)8.if(Aj=m)count+;9.if(count=n/2)flag=FALSE;10.11.return flag;12.283.时间复杂性估计时间复杂性估计majority 算法的时间复杂性由第算法的时间复杂性由第 6 行调用行调用 dandidate 所花费所花费的时间和第的时间和第 89 行的循环决定。后者的运行时间为行的循环决定。后者的运行时间为(n)。1）假定，）假定，dandidate 算法第算法第 610 行的循环体每次

23、只处理行的循环体每次只处理1 对元素，就执行第对元素，就执行第 13 行的递归调用，并假定数组元素为行的递归调用，并假定数组元素为 偶数，偶数，dandidate 算法的时间复杂性为：算法的时间复杂性为：解此递归方程，可以得到解此递归方程，可以得到 0)0(1)2()(fnfnf)(2/)(nnnf293.时间复杂性估计时间复杂性估计2）如果）如果 dandidate 算法的第算法的第 610 行的循环体每次处理行的循环体每次处理 2ki 个元素个元素 ，在递归深度为，在递归深度为 m 时，就可把寻时，就可把寻 找主元素候选者的范围由找主元素候选者的范围由 n 减少到减少到1或或0而结束递归调

24、用而结束递归调用 有有 每次递归调用时循环体中的比较次数为每次递归调用时循环体中的比较次数为 总比较次数为总比较次数为)2/,1(nkmiinkmii1212ikmimiiimkk112)12(mn)(nO30五五 整数划分问题的递归算法整数划分问题的递归算法 1.整数划分问题整数划分问题 2.递归式的推导递归式的推导 3.算法描述算法描述 311.整数划分问题整数划分问题1）用一系列正整数之和的表达式来表示一个正整数，称为整）用一系列正整数之和的表达式来表示一个正整数，称为整 数的划分。数的划分。例：例：7 可划分为：可划分为：76+15+2，5+1+14+3，4+2+1，4+1+1+13+

25、3+1，3+2+1+1，3+1+1+1+12+2+2+1，2+2+1+1+1，2+1+1+1+1+11+1+1+1+1+1+1 上述任何一个表达式都称为整数上述任何一个表达式都称为整数 7 的一个划分的一个划分 321.整数划分问题整数划分问题2）正整数）正整数 n 的不同的划分个数称为正整数的不同的划分个数称为正整数 n 的划分数，记为的划分数，记为 p(n)3）求正整数）求正整数 n 的划分数称为整数划分问题的划分数称为整数划分问题 332.递归式的推导递归式的推导1）定义两个函数：）定义两个函数：r(n,m)：正整数：正整数 m 的划分中加数含的划分中加数含 m 而不含大于而不含大于 m

26、 的所的所 有划分数。有划分数。q(n,m)：正整数：正整数 m 的划分中加数小于或等于的划分中加数小于或等于 m 的所有划的所有划 分数。分数。例：在例：在 7 的划分中：的划分中：含含 6 而不含大于而不含大于 6 的划分有：的划分有：6+1，因此，因此，r(7,6)=1；含含 5 而不含大于而不含大于 5 的划分有：的划分有：5+2，5+1+1，因此，因此，r(7,5)=2；含含 4 而不含大于而不含大于 4 的划分有：的划分有：4+3，4+2+1，4+1+1+1，因此，因此，r(7,4)=3；含含 3 而不含大于而不含大于 3 的划分有：的划分有：3+3+1，3+2+1+1，3+1+1

27、+1+1，因此，因此，r(7,3)=3；342.递归式的推导递归式的推导2）q(n,m)和和 r(n,m)的关系：的关系：从加数小于或等于从加数小于或等于 6 的划分数：的划分数：得：得：(4.1.1)13)1,7()2,7()3,7()4,7()5,7()6,7()6,7(rrrrrrqmiinrmnq1),(),(11),(),(mimnrinr),()1,(mnrmnq352.递归式的推导递归式的推导 r(n,m)等于整数等于整数 n-m 的不含大于的不含大于 m 的划分数：的划分数：例，例，r(7,3)是整数是整数 7 含有含有 3 而不含大于而不含大于 3 的所有划分的个的所有划分的

28、个 数：数：3+3+1，3+2+1+1，3+1+1+1+1 同时也是整数同时也是整数 7-3=4 的不含大于的不含大于 3 的划分数：的划分数：3+1，2+1+1，1+1+1+1 因此，有：因此，有：(4.1.2),(),(mmnqmnr362.递归式的推导递归式的推导4）递归式：）递归式：由式由式(4.1.1)和式和式(4.1.2)可得下面递归关系：可得下面递归关系：对所有的正整数对所有的正整数 n，有：有：n 的划分不可能包含大于的划分不可能包含大于 n 的加数的加数 整数整数 1 只有一个划分，而不管只有一个划分，而不管 m 有多大有多大 对所有整数对所有整数 n，含，含 1 而不含大于

29、而不含大于 1 的划分只有一个，的划分只有一个，),()1,(),(mmnqmnqmnq1),(nnr1)1,(),(nnqnnqnmnnqmnq),(),(1),1(mq1)1,(nq373.算法描述算法描述 1.int q(int n,int m)2.3.if(n1|m1)return 0;4.else if(n=1|m=1)return 1;5.else if(nm)return q(n,n);6.else if(n=m)return q(n,n-1)+1;7.else return q(n,m-1)+q(n-m,m);8.384.2 分治法分治法 一一 分治法的分治法的例子例子 二二

30、分治法的设计原理分治法的设计原理 三三 快速排序快速排序 四四 多项式乘积的分治算法多项式乘积的分治算法 五五 平面点集最接近点对问题平面点集最接近点对问题 六六 选择问题选择问题 七七 残缺棋盘问题残缺棋盘问题 39一一 分治法的例子分治法的例子 1.最大最小问题的分治算法最大最小问题的分治算法 2.合并排序的分治算法合并排序的分治算法 401.最大最小问题的分治算法最大最小问题的分治算法 1）最大最小问题的一般算法最大最小问题的一般算法 2）分治法解最大最小问题的算法描述分治法解最大最小问题的算法描述 3）分治法解最大最小问题的过程分治法解最大最小问题的过程 4）分治法解最大最小问题的分析

31、分治法解最大最小问题的分析 411）最大最小问题的一般算法）最大最小问题的一般算法 1.void max_min(int A,int&e_max,int&e_min,int n)2.3.int i;4.e_max=A0;e_min=A0;5.for(i=2;i=n;i+)6.if(A i e_max)e_max=A i;8.9.输入规模为输入规模为 n 时，元素比较次数是时，元素比较次数是 2(n 1)422）分治法解最大最小问题的算法描述分治法解最大最小问题的算法描述 1.void maxmin(int A,int&e_max,int&e_min,int low,int high)2.int

32、 mid,x1,y1,x2,y2;4.if(high-low low)mid=(high low)/2;merge_sort(A,low,mid);merge_sort(A,mid+1,high);merge(A,low,mid,high,high low);472）算法的分析算法的分析（1）merge 的时间复杂性：的时间复杂性：最好：最好：n/2 最坏：最坏：n 1（2）算法分析）算法分析 f(n)=2f(n/2)+n 1 f(1)=0 令令 n=2k h(k)=2h(k-1)+2k 1 h(0)=0482 算法的分析算法的分析 h(k)=2h(k-1)+2k 1 h(0)=0 h(k)=

33、2(2h(k-2)+2k-1 1)+2k 1 =22h(k-2)+2*2k 21 20 =22(2h(k-3)+2k2 1)+2k 21 20 =23 h(k-3)+3*2k 22 21 20 =2k h(0)+k*2k 2k-1 21 20 =k*2k (2k 1)=nlogn n+149二二 分治法的设计原理分治法的设计原理 1.分治法的一般描述分治法的一般描述 2.分治法的设计步骤分治法的设计步骤 3.分治法的时间复杂性分治法的时间复杂性 501.分治法的一般描述分治法的一般描述divide_and_conquer(P(n)if(n=)return adhoc(P(n);else div

34、ide into smaller subinstances ,;for(i=1;i 1，n 很大时，它确定了算法的实际性能很大时，它确定了算法的实际性能 mkb+)1-m(hk=)m(hm1mkb+)kb+)2m(hk(k=)m(h=)n(f-m2kb2+)2m(hk=-=mmkbm+)0(hk=nlognb+n=knlognbk553）分治法的时间复杂性）分治法的时间复杂性定理定理 令令 a,c 是非负整数，是非负整数，b,d,x 是非负常数，对某个非是非负常数，对某个非 负整数负整数 k，有，有 ，则递归方程，则递归方程 f(1)=d 的解为：的解为：令令 x=1，有：，有：kc=nxbn

35、+)c/n(af=)n(fxxcn)n(ccn)n(alogc564）子问题规模对时间复杂性的影响）子问题规模对时间复杂性的影响定理定理 令令 b,d 和和 ,是大于是大于 0 的常数，则递归方程的常数，则递归方程 f(1)=b f(n)=f(n )+f(n )+bn 的解为：的解为：f(n)=(nlogn)当当 时，有：时，有：f(n)bn/(1 )=(n)1c2c1c2c1=c+c211c+c211c2c57三三 快速排序快速排序 1.快速排序的思想方法快速排序的思想方法 2.序列的划分算法序列的划分算法 3.快速排序算法的描述快速排序算法的描述 4.最坏情况分析最坏情况分析 5.平均情况

36、分析平均情况分析 581.快速排序的思想方法快速排序的思想方法把序列就地划分为两个子序列，使第一个子序列的所有元把序列就地划分为两个子序列，使第一个子序列的所有元素都小于第二个子序列的所有元素，不断地进行这样的划素都小于第二个子序列的所有元素，不断地进行这样的划分，最后构成分，最后构成 n 个子序列，每个子序列只有一个元素，个子序列，每个子序列只有一个元素，这时，整个序列就是按递增顺序排序的序列了这时，整个序列就是按递增顺序排序的序列了592.序列的划分算法序列的划分算法1）枢点元素：给定序列）枢点元素：给定序列 ，如果存在元素，如果存在元素 ，使得对所有的，使得对所有的 i,1 i k，都有

37、，都有 ，对所，对所 有的有的 j,k j n，都有都有 ，就称，就称 是这个序列是这个序列 的枢点（的枢点（pivot）元素。）元素。把序列的第一个元素作为枢点元素，重新排列这个序把序列的第一个元素作为枢点元素，重新排列这个序 列列n21a,a,akakiaa kjaa ka602）序列的划分算法的描述）序列的划分算法的描述 2.int split(Type A,int low,int high)3.int k,i=low;5.Type x=Alow;6.for(k=low+1;k=high;k+)7.if(Ak=x)8.i=i+1;9.if(i!=k)swap(Ai,Ak);11.12.1

38、3.swap(Alow,Ai);14.return i;15.返回值：枢点元素的位置返回值：枢点元素的位置 n 个元素的序列，需执行个元素的序列，需执行 n 1 次元素比较次元素比较0 1 2 3 4 5 6 7ki5 8 4 9 3 6 7 21 02 14 834 238567 32925613.快速排序算法的描述快速排序算法的描述 2.void quick_sort(Type A,int low,int high)3.4.int k;5.if(low high)6.k=split(A,low,high);7.quick_sort(A,low,k-1);8.quick_sort(A,k+1

39、,high);9.10.624.最坏情况分析最坏情况分析元素已按递增或递减顺序排列，处于最坏的情况。元素已按递增或递减顺序排列，处于最坏的情况。split 所得到的枢点元素位置，或者使子序列的开始位置，或者所得到的枢点元素位置，或者使子序列的开始位置，或者是子序列的结束位置，是子序列的结束位置，第第 i 次划分次划分 子序列长度子序列长度 所执行的元素比较次数所执行的元素比较次数 i=1 1 n 1 n 1 i=2 1 n 2 n 2 算法算法quick_sort所执行的元素比较的总次数是：所执行的元素比较的总次数是：)n(=)1n(n21=0+1+)2n(+)1n(2-635.平均情况分析平

40、均情况分析假定所有元素的关键字的值都不相同，被选取作为枢点元假定所有元素的关键字的值都不相同，被选取作为枢点元素的可能性都为素的可能性都为 1/n。枢点元素经。枢点元素经 split 重新排列后，位重新排列后，位于序列的第于序列的第 k 位置，位置，1 k n，则枢点元素左边的元素个，则枢点元素左边的元素个数有数有 k 1 个，右边的元素个数有个，右边的元素个数有 n k 个。有递归方程个。有递归方程 f(0)=0 因为：因为：有：有：)1)-n(+)k-n(f+)1-k(f(n1=)n(fn1=k-1n0=kn1=kn1=k)k(f=)kn(f=)1n(f+)1(f+)0(f=)1-k(f-

41、1n0=k)k(fn2+)1n(=)n(f64平均情况分析（续平均情况分析（续 1）两边乘以两边乘以 n：(1)用用 n 1 取代取代 n：(2)(1)(2)得：得：两边除以两边除以 n(n+1)：令令 h(n)=f(n)/(n+1)得：得：h(0)=0-1n0=k)k(fn2+)1n(=)n(f-1n0=k)k(f2+)1n(n=)n(fn-2n0=k)k(f2+)2n()1n(=)1n(f)1n()1n(2+)1n(f)1+n(=)n(fn-)1+n(n)1n(2+n)1n(f=1+n)n(f-)1+n(n)1n(2+)1-n(h=)n(h-65平均情况分析（续平均情况分析（续 2）h(0

42、)=0)1+n(n)1n(2+)1-n(h=)n(h-n1=kn1=kn1=kk121+k22=)1+k(k)1k(2=)n(hn1=k1+n2=kk12-k14=1+nn4k12=n1=k-n1=kn1=kk12-1-1+n1+k14=66平均情况分析（续平均情况分析（续 3）h(n)=2lnn-(1)=2logn/loge-(1)=1.44 logn f(n)=(n+1)h(n)=1.44 nlogn1+nn4k12=n1=k-67四四 多项式乘积和大整数乘法多项式乘积和大整数乘法 1.多项式的划分原理多项式的划分原理 2.多项式乘积分治算法的实现多项式乘积分治算法的实现 3.多项式乘积分

43、治算法的分析多项式乘积分治算法的分析 681.多项式的划分原理多项式的划分原理两个阶多项式：两个阶多项式：令：令：有有因为：因为：所以：所以：nnxaxaaxp10)(nnxbxbbxq10)(2/10)()()(nxxPxpxp2/10)()()(nxxqxqxqnnxxqxPxxqxpxqxpxqxpxqxp)()()()()()()()()()(112/011000)()()()(1010 xqxqxPxp)()()()()()()()(01101100 xqxPxqxPxqxPxqxP)()()()(0110 xqxPxqxP)()()()()()()()(11001010 xqxPx

44、qxPxqxqxpxP691.多项式的划分原理多项式的划分原理令：令：(4.2.23)(4.2.24)(4.2.25)有：有：(4.2.26)1）把多项式划分成只有）把多项式划分成只有 n/2 项系数的多项式，项系数的多项式，2）利用式（）利用式（4.2.23）、式（）、式（4.2.24）、式（）、式（4.2.25）分别计）分别计 算只有算只有 n/2 项系数的项系数的 3 个多项式的乘积，个多项式的乘积，3）利用式（）利用式（4.2.26），把），把 3 个多项式的乘积合并成一个多项个多项式的乘积合并成一个多项 式的乘积。式的乘积。4）多项式的划分过程一直进行到只有两个系数为止，这时）多项式

45、的划分过程一直进行到只有两个系数为止，这时 就直接对只有两个系数的多项式进行计算就直接对只有两个系数的多项式进行计算)()()(000 xqxpxr)()()(111xqxpxr)()()()()(10102xqxqxpxPxrnnxxrxxrxrxrxrxqxp)()()()()()()(12/102070 2.多项式乘积分治算法的实现多项式乘积分治算法的实现 1.void poly_product(float p,float q,float r0,int n)2.3.int k,i;4.float*r1,*r2,*r3;5.r1=new float2*n-1;/*多项式乘积的缓冲区多项式乘

46、积的缓冲区*/6.r2=new float2*n-1;7.r3=new float2*n-1;8.for(i=0;i2*n-1;i+)/*缓冲区清缓冲区清0*/9.r0i=r1i=r2i=r3i=0;10.if(n=2)/*只有两项系数，直接计算只有两项系数，直接计算*/11.product(p,q,r0);71 2.多项式乘积分治算法的实现多项式乘积分治算法的实现 12.else 13.k=n/2;/*项数划分为原来的一半项数划分为原来的一半*/14.poly_product(p,q,r0,k);/*递归计算递归计算r0*/15.poly_product(p+k,q+k,r1+2*k,k);

47、/*递归计算递归计算r1*/16.plus(p,p+k,r2+k,k);/*计算计算 p0+p1*/17.plus(q,q+k,r3,k);/*计算计算 q0+q1*/18.poly_product(r2+k,r3,r2+k,k);/*递归计算递归计算r2*/19.mins(r2+k,r0,2*k-1);/*计算计算r2 r0 r1*/20.mins(r2+k,r1+2*k,2*k-1);21.plus(r0+k,r2+k,r0+k,2*k-1);/*合并结果合并结果*/22.plus(r0+2*k,r1+2*k,r0+2*k,2*k-1);23.24.delete r1;25.delete

48、r2;26.delete r3;27.72 3.多项式乘积分治算法的分析多项式乘积分治算法的分析 1）时间复杂性：列出如下递归方程：）时间复杂性：列出如下递归方程：方程改写成：方程改写成：25)2/(3)(27)2(nnnfnfnf225)1(3)(17)1(nkhkhkhkkkkhkh25)25)2(3(3)(1kkkh235235)2(30112)2323(5)1(30221kkkhikkiik2353372073 3.多项式乘积分治算法的分析多项式乘积分治算法的分析 20235337kiiknnnkk1023103371nk1039nn1093log)(3logn74 3.多项式乘积分治

49、算法的分析多项式乘积分治算法的分析 2.空间复杂性：如果输入规模为空间复杂性：如果输入规模为 n，算法需要分配，算法需要分配 6n 个个 工作单元作为多项式乘积的缓冲区。递归深度每增加工作单元作为多项式乘积的缓冲区。递归深度每增加 1，所分配的缓冲区的大小就减少一半。当，所分配的缓冲区的大小就减少一半。当 时，时，递归深度为递归深度为 k，则递归栈所需要的工作空间为：，则递归栈所需要的工作空间为：kn 2)12(62611kkii612n)(n75五五 平面点集最接近点对问题平面点集最接近点对问题 1.平面点集两点之间的距离平面点集两点之间的距离 2.分治法解最接近点对问题的思想方法分治法解最

50、接近点对问题的思想方法 3.的求取方法的求取方法 4.有关的数据结构有关的数据结构 5.实现步骤实现步骤 6.算法描述算法描述 7.算法分析算法分析 cd761.平面点集两点之间的距离平面点集两点之间的距离平面上平面上 n 个点的点集个点的点集 S，点，点 及及 之间的距离定义为：之间的距离定义为：称为点称为点 和和 的欧几里德距离的欧几里德距离)y,x(=p111)y,x(=p22222122121)yy(+)xx(=)p,p(d-)p,p(d211p2p772.分治法解最接近点对问题的思想方法分治法解最接近点对问题的思想方法1）S 中的点按中的点按 x 坐标的递增顺序排序坐标的递增顺序排序