1、 第三章第三章 分治算法分治算法一、一、分治算法基本思想分治算法基本思想二、二、典型典型实例实例三、三、分分治算法的分析技术治算法的分析技术四、四、难解问题难解问题问题：找出伪币找出伪币l 给你一个装有给你一个装有1 6枚硬币的袋子。枚硬币的袋子。1 6枚硬币中有枚硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这枚伪造的硬币。要轻一些。你的任务是找出这枚伪造的硬币。l 为了帮助你完成这一任务，将提供一台可用来比为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，比如天平。利用这台仪较两组硬币重量的仪器，比如天平。
2、利用这台仪器，可以知道两组硬币的重量是否相同。器，可以知道两组硬币的重量是否相同。方法1l 任意取1枚硬币，与其他硬币进行比较，若发现轻者，这那枚为伪币。最多可能有15次比较。方法2l 将硬币分为8组，每组2个，每组比较一次，若发现轻的，则为伪币。最多可能有8次比较。方法3分析l上述三种方法上述三种方法,分别需要比较分别需要比较15次次,8次次,4次次,那么形成比较次数差异的根本原因在哪里那么形成比较次数差异的根本原因在哪里?l方法方法1:每枚硬币都至少进行了一次比较每枚硬币都至少进行了一次比较,而而有一枚硬币进行了有一枚硬币进行了15次比较次比较l方法方法2:每一枚硬币只进行了一次比较每一枚
3、硬币只进行了一次比较l方法方法3:将硬币分为两组后一次比较可以将将硬币分为两组后一次比较可以将硬币的范围缩小到了原来的一半硬币的范围缩小到了原来的一半,这样充分这样充分地利用了只有地利用了只有1枚伪币的基本性质。枚伪币的基本性质。一、分治策略的基本思想一、分治策略的基本思想 1 基本思想基本思想 对于一个规模为n的问题，若该问题可以容易地解决(比如说规模n较小)，则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并，得到原问题的解。这种算法设计策略叫做分治法(divide and conquer)。分治法在每一层递归上
4、由三个步骤组成：(1)划分(divide)：将原问题分解为若干规模较小、相互独立、与原问题形式相同的子问题。(2)解决(conquer)：若子问题规模较小，则直接求解；否则递归求解各子问题。(3)合并(combine)：将各子问题的解合并为原问题的解。分治思想分治思想问题问题S问题问题S问题问题SS的解的解问题问题S1问题问题S2问题问题Si问题问题SnS1的解的解S2的解的解Si的解的解Sn的解的解问题的分解问题的分解子集解的合并子集解的合并子问题求子问题求解解分治策略的解题思路 if 问题不可分问题不可分then begin 直接求解；直接求解；返回问题的解；返回问题的解；end else
5、 begin 对原问题进行分治；对原问题进行分治；递归对每一个分治的部分求解递归对每一个分治的部分求解 归并整个问题，得出全问题的解；归并整个问题，得出全问题的解；end;n该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；n该问题可以分解为若干个规模较小的相同问题，即该该问题可以分解为若干个规模较小的相同问题，即该问题具有问题具有最优子结构性质最优子结构性质n利用该问题分解出的子问题的解可以合并为该问题的利用该问题分解出的子问题的解可以合并为该问题的解；解；n该问题所分解出的各个子问题是相互独立的，即子问该问题所分解出的各个子问题是相互独立的，即子问
6、题之间不包含公共的子问题。题之间不包含公共的子问题。因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法贪心算法或动态规划动态规划。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划动态规划较好。二分搜索技术分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这
7、个问题满足分治法的第一个适用条件分析：比较x和a的中间元素amid，若x=amid，则x在L中的位置就是mid；如果xai，同理我们只要在amid的后面查找x即可。无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。分析：很显然此问题分解出的子问题相互独立，即在ai的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个元素个元素中找出一特定元素中找出一特定元素x。分析：分析：该问题的规模缩小到一定的程度就可以容易
8、地解决；该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个元素个元素中找出一特定元素中找出一特定元素x。据此容易设计出二分搜索算法二分搜索算法：public static int binarySearch(int a,int x,int n)/在 a0=a1=.=an-1 中搜索 x /找到x返回其在数组中的位置,否则返回-1 int left=0;int right=n-1;while(left amiddle)left=middle+1;
9、else right=middle-1;return-1;/未找到x 算法复杂度分析：算法复杂度分析：每执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(log2n)次。循环体内运算需要O(1)时间，因此整个算法在最坏情况下的计算时间复杂性为O(log2n)。二分搜索技术二分搜索技术v算法复杂度分析：v二分搜索算法在最坏情况下的计算时间复杂性为O(log2n)。复杂度分析复杂度分析T(n)=O(log2n)11)2/()1()(nnbnTOnTv人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的
10、k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。基本思想：基本思想：将待排序元素分成大小大致相同的将待排序元素分成大小大致相同的2个子集合，分个子集合，分别对别对2个子集合进行排序，最终将排好序的子集合合并成为所个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。要求的排好序的集合。二、分治算法的经典实例合合并排序1.合并排序合并排序8 3 2 9 7 1 5 48 3 2 97 1 5 48 32 97 15 4832971543 82 91 74 52 3 8 91 4
11、5 71 2 3 4 5 7 8 9基本思想：基本思想：将待排序元素分成大小大致相同的将待排序元素分成大小大致相同的2个子集合，分个子集合，分别对别对2个子集合进行排序，最终将排好序的子集合合并成为所个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。要求的排好序的集合。void MergeSort(Type a,int left,int right)if(left1)copy A0.n/2-1 to B0.n/2-1;copy An/2.n-1 to C0.n/2-1;Mergesort(B0.n/2-1);Mergesort(C0.n/2-1);Merge(B,C,A);算
12、法算法 Merge(B0.p-1,C0.q-1),A0.p+q-1)/将两个有序数组合并成一个有序数组将两个有序数组合并成一个有序数组/输入：两个有序数组输入：两个有序数组B0.p-1和和C0.q-1/输出：非降序列数组输出：非降序列数组A-0.p+q-1i0;j0;k0;while(ip and j1当当n=2k时，可得时，可得T(n)=2(2T(n/4)+n/2)+n =4T(n/4)+2n =4(2T(n/8)+n/4)+2n =2kT(1)+kn =nlogn如果如果2kn2k+1，有有T(n)T(2k+1)，有，有T(n)=(nlogn)Memory Time 冒泡300K7483M
13、S合并684K171MS思考v当实例较少时，合并排序的效率如何？v合并排序的空间效率如何？v合并排序对特殊数据是否会退化？v在划分子问题时是否可以3等分，如果可以，效率如何？&最坏时间复杂度：最坏时间复杂度：O(nlogn)&平均时间复杂度：平均时间复杂度：O(nlogn)&辅助空间：辅助空间：O(n)合并排序2.快速排序v基本思想 选取A的某个元素t=As，然后将其他元素重新排列，使A0.n-1中所有在t以前出现的元素都小于或等于t，而在t之后出现的元素都大于或等于t。A0A1As-1AsAs+1An-1t划分元素An-1AktAjA1A0经过一次划分后经过一次划分后每个元素都小于或等于t每
14、个元素都大于或等于t划分的实现p全部pp.p全部 p ijp全部p p p全部 p i=jp全部p=p全部 p ij划分元素（中轴）的选取：划分元素（中轴）的选取：可以随机选取，最简单的选择策略是数组第一个元素可以随机选取，最简单的选择策略是数组第一个元素划分的实现思想划分的实现思想同时从左、右开始扫描，左边找到一个比划分元素大的，右边找到同时从左、右开始扫描，左边找到一个比划分元素大的，右边找到一个比划分元素小的，然后交换两个元素的位置。一个比划分元素小的，然后交换两个元素的位置。27划分实例划分实例 27 99 0 8 13 64 86 16 7 10 88 25 90 i j 27 25
15、 0 8 13 64 86 16 7 10 88 99 90 i j 27 25 0 8 13 10 86 16 7 64 88 99 90 i j 27 25 0 8 13 10 7 16 86 64 88 99 90 j i 16 25 0 8 13 10 7 27 86 64 88 99 90 快速排序算法算法 Quicksort(Al.r)/用Quicksort对子数组排序/输入：数组A0.n-1中的子数组/输出：非降序的子数组Al.rif(l1Tbest(n)=(nlogn)Tworst(n)=(n+1)+n+(n-1)+.+3=(n2)Tavg(n)=0n=0,1(n+1)+Tav
16、g(s)+Tavg(n-1-s)/n n1Tavg(n)2nlnn 1.38nlogn思考：平均效率的递推式是如何思考：平均效率的递推式是如何得到的，如何计算？得到的，如何计算？30T(n)2 T(n/2)n 2(2T(n/4)n/2)n4T(n/4)2n 4(2T(n/8)n/4)2n8T(n/8)3n nT(1)nlog2nO(nlog2n)因此，时间复杂度为因此，时间复杂度为O(nlog2n)。在在最好情况最好情况下，每次划分对一个记录定位后，该记录的左侧子下，每次划分对一个记录定位后，该记录的左侧子序列与右侧子序列的长度相同。在具有序列与右侧子序列的长度相同。在具有n个记录的序列中，一
17、次个记录的序列中，一次划分需要对整个待划分序列扫描一遍，则所需时间为划分需要对整个待划分序列扫描一遍，则所需时间为O(n)。设。设T(n)是对是对n个记录的序列进行排序的时间，每次划分后，正好个记录的序列进行排序的时间，每次划分后，正好把待划分区间划分为长度相等的两个子序列，则有：把待划分区间划分为长度相等的两个子序列，则有：31因此，时间复杂度为因此，时间复杂度为O(n2)。在在最坏情况最坏情况下，待排序记录序列正序或逆序，每次划分只下，待排序记录序列正序或逆序，每次划分只得到一个比上一次划分少一个记录的子序列（另一个子序得到一个比上一次划分少一个记录的子序列（另一个子序列为空）。此时，必须
18、经过列为空）。此时，必须经过n-1次递归调用才能把所有记录次递归调用才能把所有记录定位，而且第定位，而且第i趟划分需要经过趟划分需要经过n-i次关键码的比较才能找到次关键码的比较才能找到第第i个记录的基准位置，因此，总的比较次数为：个记录的基准位置，因此，总的比较次数为：)()1(21211nOnninni）（32在在平均情况平均情况下，设基准记录的关键码第下，设基准记录的关键码第k小（小（1kn），则），则有：有：这是快速排序的平均时间性能，可以用归纳这是快速排序的平均时间性能，可以用归纳法证明，其数量级也为法证明，其数量级也为O(nlog2n)。nknknkTnnkTknTnnT11)(2
19、)1()(1)(在快速排序中，记录的比较和交换是从两端向中间进行的，在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。因而总的比较和移动次数较少。快速排序 快速排序算法的性能取决于划分的对称性。通过修改算法快速排序算法的性能取决于划分的对称性。通过修改算法partitionpartition，可以设计出采用随机选择策略的快速排序算法。在，可以设计出采用随机选择
20、策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在快速排序算法的每一步中，当数组还没有被划分时，可以在ap:rap:r中随机选出一个元素作为划分基准，这样可以使划分基准中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。的选择是随机的，从而可以期望划分是较对称的。templateint RandomizedPartition(Type a,int p,int r)int i=Random(p,r);Swap(ai,ap);return Partition(a,p,r);&最坏时间复杂度：最坏时间复杂度：O(n2)&平均时间复杂度
21、：平均时间复杂度：O(nlogn)&辅助空间：辅助空间：O(n)或或O(logn)快速排序快速排序算法分析v快速排序在平均情况下仅比最优情况多执行38的比较操作。v它的最内循环效率非常高，在处理随机排列数组时，速度比合并排序快。v算法优化 更好的划分元素选择方法：三平均分区 当子数组足够小时改用更简单得排序方法 将分区分为三块而不是原来的两块：一块是小于中轴值的所有元素，一块是等于中轴值的所一块是等于中轴值的所有元素有元素，另一块是大于中轴值的所有元素作业v1、实践环节自己实现合并排序和快速排序v2、小组讨论内容：快速排序算法及其改进手段：利用网络资源查阅相关资料形式：以小组为单位提交论文（W
22、ORD文档）在含有n个不同元素的集合中同时找出它的最大值和最小值(maximum&minimum)的最简单方法是将元素逐个进行比较。算法中用max和min分别表示最大值和最小值。算法描述如下：MAXMIN(A)1 max min A1 2 for i 2 to n 3 if Aimax 4 then max Ai 5 else if AiAj 5 then fmax Ai 6 fmin Aj 7 else fmax Aj 8 fmin Ai 9 else mid (i+j)/2 10 REC-MAXMIN(i，mid，gmax，gmin)11 REC-MAXMIN(mid+1，j，hmax，h
23、min)12 fmax maxgmax，hmax 13 fmin mingmin，hmin 设T(n)表示算法所需的元素比较次数，则可得算法的递归方程为 2)2/()2/(10)(nTnTnTn=1 n=2 n2 假设n为2的幂，化简T(n)可得 2)2/(210)(nTnTn=1 n=2 n2 T(n)=2T(n/2)+2 =2(2T(n/4)+2)+2 =4T(n/4)+4+2 =2k-1T(2)+=2k-1+2k-2 =3n/2-2 112kii这表明算法的最坏、平均以及最好情况的元素比较次数为3n/2-2。事实上，至多进行3n/2次比较是找出最小值和最大值的充分条件。我们并不将每个元素
24、与最大值和最小值都进行比较，因为这样每个元素需要进行两次比较。下面我们成对处理元素。首先，输入元素成对相互进行比较，并将较小者与当前最小值比较，较大者与当前最大值比较。这样每两个元素进行三次比较。设置当前最小元素和最大元素的初始值，与n的奇偶性有关。当n为奇数时，我们将最小值和最大值都设为第一个元素，然后，将其余元素成对处理；当n为偶数时，我们在前两个元素之间进行一次比较，决定最大值和最小值的初始值，然后，将其余元素成对处理。以下分析上述算法的比较次数。如果n为奇数，那么需进行3n/2次比较；如果n为偶数，我们首先在前两个元素之间进行一次比较，然后进行3(n-2)/2次比较，总共进行3n/2-
25、2次比较。因此，不论在哪一种情况下，比较的次数至多为3n/2 可以证明，任何基于比较的找最大值和最小值的算法，其元素比较次数下界为3n/2-2。在这种意义下，算法REC-MAXMIN是最优的。但是REC-MAXMIN也有其不足之处，它所要求的存储空间较大，即算法中的每次递归调用都需要保留i，j，fmax，fmin的值及返回地址。扩展：找第二大元素扩展：找第二大元素通常算法：顺序比较通常算法：顺序比较 1顺序比较找到最大顺序比较找到最大max;2从剩下的从剩下的n 1个数中找最大，就是第二大个数中找最大，就是第二大second复杂性：复杂性：W(n)=n 1+n 2=2n 3锦标赛算法：锦标赛算
26、法：两两分组比较，大者进入下一轮两两分组比较，大者进入下一轮 每个元素用数表记录每次比较时小于自己的元素每个元素用数表记录每次比较时小于自己的元素46算法算法 FindSecond输入：输入：n个数的数组个数的数组L输出：输出：Second 1k n 2将将 k 个元素两两一组，分成个元素两两一组，分成 k/2 组组 3每组的每组的2个数比较，找到较大的数个数比较，找到较大的数 4将被淘汰的较小的数在淘汰它的数所指向的链表中将被淘汰的较小的数在淘汰它的数所指向的链表中 做记录做记录 5if k 为奇数为奇数 then k k/2 +1 6else k k/2 7if k1 then goto
27、2 8max 最大数最大数 9Second max 的链表中的最大的链表中的最大锦标赛算法锦标赛算法47max在第一阶段的分组比较中总计进行了在第一阶段的分组比较中总计进行了 logn 次比较次比较.算法时间复杂度是算法时间复杂度是 W(n)=n 1+log n 1=n+log n 2.时间复杂度分析时间复杂度分析48 问题：选第问题：选第 k 小小.输入：数组输入：数组 S,S的长度的长度 n,正整数正整数 k,1 k n.输出：第输出：第 k 小的数小的数通常算法通常算法 1排序排序 2找第找第 k 小的数小的数时间复杂性：时间复杂性：O(nlogn)一般性选择问题一般性选择问题分治法设计
28、思路利用PARTITION过程。如果划分元素v测定在A(j)的位置上，则有j-1个元素小于或等于A(j)，且有n-j个元素大于或等于A(j)。此时：若k=j，则A(j)即是第k小元素；否则，若kj，则第k小元素将出现在A(j+1:n)中。基于划分的选择算法A128=8,33,17,51,57,49,35,11,25,37,14,3,2,13,52,12,6,29,32,54,5,16,22,23,7,61,36,9，求A的中值元素，即第14小元素。(k=14)8,33,17,51,57,49,35,11,25,37,14,3,2,13,52,12,6,29,32,54,5,16,22,23,7
29、,61,36,93,7,5,6,2,8,11,25,37,14,35,49,13,52,12,57,29,32,54,51,16,22,23,17,61,36,33,9jk，在右边区间找第k(=14-6=8)小元素9,11,37,14,35,49,13,52,12,57,29,32,54,51,16,22,23,17,61,36,33,25jk，在左边区间找第k(=6)小元素j=14总结归纳l 分治是一种解题的策略，它的基本思想是：分治是一种解题的策略，它的基本思想是：“如果整个问如果整个问题比较复杂，可以将问题分化，各个击破。题比较复杂，可以将问题分化，各个击破。”l 分治包含分治包含“分分
30、”和和“治治”两层含义，如何分，分后如何两层含义，如何分，分后如何“治治”成为解决问题的关键所在成为解决问题的关键所在l 不是所有的问题都可以采用分治，只有那些能将问题分成不是所有的问题都可以采用分治，只有那些能将问题分成与原问题类似的子问题，并且归并后符合原问题的性质的与原问题类似的子问题，并且归并后符合原问题的性质的问题，才能进行分治问题，才能进行分治l 分治可进行二分，三分等等，具体怎么分，需看问题的性分治可进行二分，三分等等，具体怎么分，需看问题的性质和分治后的效果。质和分治后的效果。l 只有深刻地领会分治的思想，认真分析分治后可能产生的只有深刻地领会分治的思想，认真分析分治后可能产生的预期效率，才能灵活地运用分治思想解决实际问题。预期效率，才能灵活地运用分治思想解决实际问题。
