1、学习要点学习要点:n理解递归的概念。n掌握设计有效算法的分治策略。n通过下面的范例学习分治策略设计技巧。（1）二分搜索技术；（2）大整数乘法；（3）Strassen矩阵乘法；（4）合并排序（5）快速排序；（6）线性时间选择；n将要求解的较大规模的问题分割成k个更小规模的子问题。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=n对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。2.1 n直接或间接地调用自身的算法称为递归算法递归算法。用函数自身给出定义的函数称为递归函数递归函数。n由分治法产生的子问题
2、往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与子问题与原问题类型一致而其规模却不断缩小原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。n分治与递归像一对孪生兄弟，经常同时应用。2.1 例例1 1 阶乘函数阶乘函数 非递归定义：非递归定义：n n！=n=n*(n-1)(n-1)*(n-2)(n-2)*1 1 阶乘函数可递归地定义为：00)!1(1!nnnnn边界条件边界条件递归方程递归方程边界条件与递归方程是递归函数的二个要素。n递归算法：int recur(int n)if(n=1)retu
3、rn 1;return n*recur(n-1);递归出口递归出口递归调用递归调用2.1 例例2 Fibonacci2 Fibonacci数列数列无穷数列1，1，2，3，5，8，13，21，34，55，称为Fibonacci数列。它可以递归地定义为：边界条件边界条件递归方程递归方程110)2()1(11)(nnnnFnFnF第n个Fibonacci数可递归地计算如下：int fibonacci(int n)if(n 0)hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);表示以塔座b为辅助塔座，将塔座上自下而上，由大到小叠在一起的-1个圆盘按规则移至塔座上并
4、按同样顺序叠放。将塔座a上的圆盘移动到塔座b上去Hanoi塔问题的复杂性分析n=1移动次数（）n移动次数（）n移动次数（）n移动次数（）n当时当时移动次数（）？移动次数（）？优点：优点：结构清晰，可读性强，而且容易用结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。为设计算法、调试程序带来很大方便。缺点：缺点：递归算法的运行效率较低，无论是递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比耗费的计算时间还是占用的存储空间都比非递归算法要多。非递归算法要多。n求Fibonacci数时有很多重复工
5、作：解决方法：解决方法：在递归算法中消除递归调用，使其在递归算法中消除递归调用，使其转化为非递归算法。转化为非递归算法。1 1、采用一个、采用一个用户定义的栈用户定义的栈来模拟系统的递归调来模拟系统的递归调用工作栈。该方法用工作栈。该方法通用性强通用性强，但本质上还是递，但本质上还是递归，只不过人工做了本来由编译器做的事情，归，只不过人工做了本来由编译器做的事情，优化效果不明显优化效果不明显。2 2、用、用递推递推来实现递归函数。来实现递归函数。3 3、通过变换能、通过变换能将一些递归转化为尾递归将一些递归转化为尾递归，从而，从而迭代求出结果。迭代求出结果。后两种方法在后两种方法在时空复杂度上
6、均有较大改善，时空复杂度上均有较大改善，但其适用范围有限但其适用范围有限。分治法的基本思想n分治法的基本思想分治法的基本思想将一个规模为n的问题分解为a个规模较小的子问题，这些子问题互相独立并且与原问题相同。通过递归地求解这些子问题，然后再将各个子问题的解合并，就可以实现对原问题的求解。分治法的求解过程分治法的求解过程分治法的求解过程n分解分解(divide)：将原问题分解为一系列子问题；：将原问题分解为一系列子问题；n递归求解递归求解(conquer)：递归求解各个子问题。若：递归求解各个子问题。若子问题足够小，则直接求解。子问题足够小，则直接求解。n合并合并(merge)：将子问题结果合并
7、成原问题的解：将子问题结果合并成原问题的解说明：某些问题不需要说明：某些问题不需要合并合并，比如二分搜索，比如二分搜索问题问题divide-and-conquer(P)if(|P|=n0)adhoc(P);divide P into smaller subinstances P1,P2,Pa;for(i=1,i=a,i+)yi=divide-and-conquer(Pi);return merge(y1,y2,ya);|P|：问题P的规模；adhoc：分治法中的基本子运算n0：阀值如果问题P的规模不超过n0，说明问题已经容易求解，不要再继续分解。利用adhoc(P)直接求解。分治法的设计模式分
8、治法的分割原则n分治法的分割原则分治法的分割原则实践实践表明：将一个问题划分成数据规模大小相数据规模大小相等的等的a个子问题个子问题的处理方法行之有效；分治法的计算效率分析n分治法的计算效率分析分治法的计算效率分析通常用递归方程来进行分析通常用递归方程来进行分析分治法将规模为n的问题分成a个规模为n/b的子问题n设分解阈值n0=1，且adhoc解规模为1的问题耗费1个单位时间n设将原问题分解为a个子问题以及用merge将a个子问题的解合并为原问题解需要使用f(n)个单位时间。n用T(n)表示该分治法divide-and-merge(P)解规模为|P|=n的问题所需要的计算时间log1log0(
9、1)1()(/)()1()(/)bbnajjjOnT naT n bf nnT nna f n bg(n)函数函数g(n)函数g(n)函数T(n)函数log1log0(1)1()(/)()1()(/)bbnajjjOnT naT n bf nnT nna f n b主方法(详见算法导论)根据这两项对结果的影响不同，分成三种情况讨论logloglog()()()()bbbaaaT nnO nnlogloglog()()(lg)(lg)bbbaaaT nnnnnnlog()()()()baT nnf nf n因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。这条特征是
10、应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法贪心算法或动态规划动态规划。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划动态规划较好。n该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；n该问题可以分解为若干个规模较小的相同问题，即该该问题可以分解为若干个规模较小的相同问题，即该问题具有问题具有最优子结构性质最优子结构性质n利用
11、该问题分解出的子问题的解可以合并为该问题的利用该问题分解出的子问题的解可以合并为该问题的解；解；n该问题所分解出的各个子问题是该问题所分解出的各个子问题是相互独立相互独立的，即子问的，即子问题之间不包含公共的子问题。题之间不包含公共的子问题。n二分搜索技术n大整数的乘法nStrassen矩阵乘法n合并排序n快速排序n线性时间选择二分搜索技术二分搜索技术分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件分析：比较x和a的中间元素amid，若x=amid，则x在L中的位置就是mid；如果xai，同理我们只要在amid的后面查找x即可
12、。无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。分析：很显然此问题分解出的子问题相互独立，即在ai的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。给定已按升序给定已按升序排好序排好序的的n个元素个元素a0:n-1，现要在这，现要在这n个元素中找个元素中找出一特定元素出一特定元素x。分析：分析：该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并
13、为原问题的解；分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。分解出的各个子问题是相互独立的。n逐个地扫描数组a中每个元素，直到找到x为止。在含有n个元素的线性表中查找一个元素在最坏情况下都需要进行n次比较，其时间复杂度为O(n)。n利用分治法分治法求解此问题,求解过程是：将n个元素分分成个数大致相等彼此独立的两半部分，分，即an/2的前面或后面两个子问题；将第n/2位置的元素与x进行比较，如果相等，则找到x，算法结束。如果xan/2,则在数组a的后半部分分继续搜索搜索x；如果xan/2,则在数组a的前半部分分继续搜索搜索x。给定已按升序排好序的给定已按升序排好序的n个
14、元素个元素a0:n-1，现要在这，现要在这n个元素中找个元素中找出一特定元素出一特定元素x。据此容易设计出二分搜索算法二分搜索算法：template int BinarySearch(Type a,const Type&x,int l,int r)while(r=l)int m=(l+r)/2;if(x=am)return m;if(x am)r=m-1;else l=m+1;return-1;算法复杂度分析：算法复杂度分析：每执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn)次。循环体内运算需要O(1)时间，因此整个算法在最坏情况
15、下的计算时间复杂性为O(logn)。大整数的乘法大整数的乘法大整数的乘法n大整数的乘法大整数的乘法问题描述n需要处理的整数超过了计算机硬件能直接处理的整数范围n浮点数计算对精度的影响解决方案n利用软件方法来实现大整数的乘法典型应用nRSA密码体系 n传统做法：需要做n*n次1位整数乘法操作，n-1次移位操作，n-1次加法操作时间复杂度为O(n2)n/2位n/2位ABX=n/2位n/2位CDY=大整数大整数X和和Y的分段的分段DCYBAXnn2/2/2,2X、Y为两个为两个n位的二进制整数位的二进制整数XY的乘积形式（1/2）BDCBADACDCBAXYnnnn2/2/2/2)(2)2)(2(形
16、式一：形式一：包括：包括：4次次n/2位整数的乘法位整数的乘法3次不超过次不超过2n位的整数加法位的整数加法2次移位次移位所有加法和移位共用所有加法和移位共用O(n)步运算步运算设设T(n)是是2个个n位整数相乘所需的运算总数位整数相乘所需的运算总数)()(1)()2/(41)1()(2nOnTnnOnTnOnTXY的乘积形式（2/2）BDBDACCDBAACXYnn2/2)(2形式二：形式二：包括：包括：3次次n/2位整数的乘法位整数的乘法6次整数加、减法次整数加、减法2次移位次移位)()()(1)()2/(31)1()(59.13lognOnOnTnnOnTnOnTp如果将大整数分成更多段
17、，用更复杂的方式把它们组合起来，将有可能得到更优的算法。p最终的，这个思想导致了快速傅利叶变换快速傅利叶变换(Fast Fourier Transform)的产生。该方法也可以看作是一个复杂的分治算法，对于大整数乘法，它能在O(nlogn)时间内解决。p是否能找到线性时间的算法？目前为止还没有结果。StrassenStrassen矩阵乘法矩阵乘法矩阵的乘法：矩阵的乘法：使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：u传统方法：O(n3)u分治法:222112112221121122211211BBBBAAAACCCC由此可得：2112
18、111111BABAC2212121112BABAC2122112121BABAC2222122122BABAC复杂度分析复杂度分析T(n)=O(n3)22)()2/(8)1()(2nnnOnTOnT2个n阶矩阵的乘积转化为计算8个n/2阶矩阵的乘积和4个n/2阶矩阵的和。2个(n/2)*(n/2)阶的矩阵加法可以在O(n2)时间内完成使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：u传统方法：O(n3)u分治法:222112112221121122211211BBBBAAAACCCC由此可得：2112111111BABAC221212
19、1112BABAC2122112121BABAC2222122122BABACu传统方法：O(n3)u分治法:为了降低时间复杂度，必须减少乘法的次数。222112112221121122211211BBBBAAAACCCC)(2212111BBAM2212112)(BAAM1122213)(BAAM)(1121224BBAM)(221122115BBAAM)(222122126BBAAM)(121121117BBAAM624511MMMMC2112MMC4321MMC731522MMMMC复杂度分析复杂度分析T(n)=O(nlog7)=O(n2.81)较大的改进较大的改进22)()2/(7)1
20、()(2nnnOnTOnT做了7次乘法运算；做了18次加减法运算；u分解：将n阶矩阵A、B分解为n/2阶子矩阵；u解决：进行7次递归计算(n/2)*(n/2)子矩阵的乘积；u合并：按C的子矩阵，对子矩阵的乘积进行加减法运算；u更快的方法?Hopcroft和Kerr已经证明(1971)，计算2个矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算22矩阵的7次乘法这样的方法了。或许应当研究或矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376)是否能找到O(n2)的算法？合并排序合并排序基
21、本思想：基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。void mergesort(Type a,int left,int right)if(leftright)/至少有2个元素 int i=(left+right)/2;/取中点 mergesort(a,left,i);mergesort(a,i+1,right);merge(a,b,left,i,right);/合并到数组b copy(a,b,left,right);/复制回数组a merge和copy可以在O(n)时间内完成，复杂度分析复杂度分析T(n)=O
22、(nlogn)渐近意义下的最优算法11)()2/(2)1()(nnnOnTOnT算法mergesort递归地调用自身，不断将子序列分成两个更小的子序列算法merge合并两个排好序的数组到新数组b中算法copy将合并后的数值段再复制到数组a中n算法mergesort存在递归过程p它将序列一分为二，直到序列只剩一个元素为止，然后不断合并2个排好序的序列；n改进思路：p将初始序列看出n个长度为1的有序子序列，然后两两归并，得到n/2个长度为2的有序子序列；再两两归并，重复直到得到一个长度为n的有序序列算法mergesort的递归过程可以消去。初始序列49 38 65 97 76 13 2738 49
23、 65 97 13 76 27第一步第二步38 49 65 97 13 27 76第三步13 27 38 49 65 76 97n自然合并排序算法：自然合并排序算法：任何数组都有现成已排好任何数组都有现成已排好序的子数组段，以此为基础排序序的子数组段，以此为基础排序4,8,3,7,1,5,6,2先进行一次线性扫描，再合并相邻排好的子数组段先进行一次线性扫描，再合并相邻排好的子数组段快速排序快速排序基本思想：基本思想：以以ap为基准元素，将数组为基准元素，将数组ap:r划分为划分为ap:q-1小小,aq和和aq+1:r大大三段三段,然后通过递归调用分别对然后通过递归调用分别对ap:q-1和和aq
24、+1:r进行快速排序。进行快速排序。说明：因排序分块进行，合并步骤省略。说明：因排序分块进行，合并步骤省略。template QuickSort(Type a,int p,int r)if(p=r)return;q=Partition(a,p,r);QuickSort(a,p,q-1);/对左半段排序对左半段排序QuickSort(a,q+1,r);/对右半段排序对右半段排序在在Partition(a,p,r)中，记录的比较和中，记录的比较和交换是交换是从两端向中间进行的从两端向中间进行的,值较大的值较大的记录交换到记录交换到aq+1,r，值较小的记录交，值较小的记录交换到换到ap,q-1。记
25、录每次移动的距离较。记录每次移动的距离较大，但总的比较和移动次数较少。大，但总的比较和移动次数较少。52 49 80 36 14 58 61 97 23 75prr23p80r14p52例如：例如：ap=52prrrptemplate Type Partition(Type a,int p,int r)Type x=ap;while(pr)while(p=x)-r;ap=ar;while(pr&ap=x)+p;ar=ap;ap=x;return p;/返回枢轴所在位置/Partition基准元素快速排序算法的复杂性分析n快速排序算法的复杂性分析快速排序算法的复杂性分析运行时间与划分是否对称有关
26、n最坏情况：最坏情况：对于一个包含n个元素的数组，被划分成两个区域，其中一个包含n-1个元素，而另一个中只有一个元素。n最好情况：最好情况：每次划分都产生两个大小为n/2的区域。)log()(1)()2/(21)1()()()(1)()1(1)1()(2nnOnTnnOnTnOnTnOnTnnOnTnOnT最好情况：最坏情况：快速排序算法在最好情况下的时间复杂性是快速排序算法在最好情况下的时间复杂性是O(nlogn)通常基于比较的排序算法的算法复杂度是通常基于比较的排序算法的算法复杂度是O(n2)快速排序算法因此得名，对规模大的问题较有效快速排序算法因此得名，对规模大的问题较有效算法设计者因为
27、这个代表性贡献而获得算法设计者因为这个代表性贡献而获得1980年的年的Turing奖奖templateint RandomizedPartition(Type a,int p,int r)int i=Random(p,r);Swap(ai,ap);return Partition(a,p,r);快速排序算法的性能取决于划分的对称性。通过修改算法partition，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在ap:r中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。&最坏时间复杂度：最坏时间复杂度：O
28、(n2)&平均时间复杂度：平均时间复杂度：O(nlogn)&辅助空间：辅助空间：O(n)或或O(logn)线性时间选择线性时间选择线性时间选择的基本思想n元素选择问题元素选择问题给定线性序集中的给定线性序集中的n个元素和一个整数个元素和一个整数k，1kn，要求找出这，要求找出这n个元素中第个元素中第k小的元素。小的元素。n当k=1时找最小元素；n当k=n时找最大元素；n当k=(n+1)/2找中位数n算法设计思想算法设计思想与快速排序算法的设计思想基本相同，即对输入数组进行递归划分，但操作上操作上只对划分出的两个只对划分出的两个子数组中的一个子数组中的一个进行进一步的递归处理进行进一步的递归处理
29、；Type RandomizedSelect(Type a,int p,int r,int k)if(p=r)return ap;int i=RandomizedPartition(p,r);/将数组划分为两部分 int j=i-p+1;/ap:i的元素个数 if(k=j)return RandomizedSelect(a,p,i,k);else return RandomizedSelect(a,i+1,r,k-j);说明：为什么只需要对其中的一个子数组进行进一步的递归处理为什么只需要对其中的一个子数组进行进一步的递归处理数组ap:r被划分成两个子数组ap:i和ai+1:r,使得ap:i中的
30、元素都不大于ai+1:r中的元素；计算ap:i中的元素个数j，如果kj,则所要找的元素就在ap:i内，否则在ai+1:r内只要对其中的一个子数组进一步的递归处理即可templateRandomizedPartition(Type a,int p,int r)int i=rand()%(r-p+1)+p;Swap(ai,ap);return Partition(a,p,r);template Type Partition(Type a,int p,int r)int i=p,j=r+1;Type x=ap;while(true)while(a+ix&ix);if(i=j)break;Swap(a
31、i,aj);ap=aj;aj=x;return j;对算法的讨论nRandomizedSelect算法在最坏情况下需要(n2)计算时间，其平均计算时间为O(n)n出发点：出发点：如果能在线性时间内找到一个划分基准，使得使得按这个基准所划分出的两个子数组的长度都至按这个基准所划分出的两个子数组的长度都至少为原数组的少为原数组的倍（倍（0011），那么就可以在最坏的情况下用O(n)时间完成选择任务说明)()()()10/9()(10/110/9nOnTnOnTnTselect在最坏情况下至少缩短组的长度递归调用所产生的子数算法比如，寻找满足要求的划分基准n按以下步骤寻找满足要求的划分基准按以下步骤
32、寻找满足要求的划分基准1.将n个输入元素划分成n/5个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法对每组中的元素进行排序，并取出每组中的中位数，共n/5个。2.递归调用算法select来找这n/5个元素的中位数。如果n/5个为偶数，就找它的两个中位数中较大的一个。以这个元素作为划分基准。注：注：假定假定n个元素都互不相等个元素都互不相等x选择划分基准选择划分基准分析4/14/1053751053105310510521052/)55(5缩短个子数组的长度都至少按此基准划分得到的两时，当个元素大于少有同理个元素小于至少有该组的中位数每组中有两个元素小于个中位数小于个中位数中，
33、有在的选择策略根据中位数 nnnxnxnnnxnnnx满足算法满足算法select的要求的要求)()(75)4/3()5/(75)(21nOnTnnTnTnCnCnT算法复杂性分析按算法所选基准x进行划分所得到的2个子数组分别至多有3n/4个元素，无论对哪一个子数组调用select都至多用T(3n/4)的时间找中位数的中位数分析n分析分析Select算法将每一组的大小定为5，并选取75作为是否进行递归调用的分界点。这两点保证了T(n)的递归式中两个自变量之和n/5+3n/4=19n/20=an,0a1使T(n)=O(n)的关键*除5和75的组合之外，还有其他选择Type Select(Type
34、 a,int p,int r,int k)if(r-p75)/75为事先设定的阈值为事先设定的阈值 用某个简单排序算法对数组用某个简单排序算法对数组ap:r排序排序;return ap+k-1;for(int i=0;i=(r-p-4)/5;i+)将将ap+5*i至至ap+5*i+4的第的第3小元素与小元素与ap+i交换位置交换位置;/找中位数的中位数，找中位数的中位数，r-p-4即上面所说的即上面所说的n-5 Type x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);int i=Partition(a,p,r,x),j=i-p+1;if(k=j)return Sel
35、ect(a,p,i,k);else return Select(a,i+1,r,k-j);考虑存在相等元素的问题Type Comparable select(int p,int r,int k)Comparable x=select(p,p+(r-p-4)/5,(r-p+6)/10);int i=patition(p,r,x),j=i-p+1;*对所有等于基准对所有等于基准x的相等元素进行汇总的相等元素进行汇总;如果如果(个数个数m1，且，且jkj+m-1)直接返回直接返回ai;否则否则 调用调用select(i+m+1,r,k-j-m);*实验题：1、算法分析题2-5 2、线性时间选择（分治
36、策略）实验数据：input.txt（共100个数据）要求找出序列中最小的元素将最小元素输出到output.txt文件中 3、主元素问题主元素问题n问题描述：问题描述：设T0:n-1是n个元素的数组，如果其中某个元素x在整个数组中的出现次数超过n/2，则称x为数组T的主元素。输入数据由文件名为input.txt的文本文件提供。n请设计一个线性时间算法，判断input中的数据是否存在主元素。在实验报告中对算法时间复杂度作出分析。n输入：文件的第1行为数组S中元素个数n；接下来的n 行中，每行有一个自然数。程序运行结束时，将计算结果输出到文件output.txt中。输出文件中包含问题的答案：找不到主元素时给出null，找到时给出主元素的值。理论作业n算法分析题n2-4、2-9、2-11、2-12
