第二章-2内容

1、 2.32.3分治法应用实例分治法应用实例 2.3.1 2.3.1 找最大值与最小值找最大值与最小值一、逐个比较法一、逐个比较法 1 1、算法思想、算法思想 在含有在含有N N个不同元素的集合中同时找出它的个不同元素的集合中同时找出它的最大值和最小值最大值和最小值(maximum&minimum)(maximum&minimum)的最简单方法的最简单方法是将元素逐个进行比较。算法中用是将元素逐个进行比较。算法中用maxmax和和minmin分别分别表示最大值和最小值。表示最大值和最小值。 2 2、算法描述如下：、算法描述如下： 3 3、分析、分析 1 1）如果数如果数组中元素按

2、照递组中元素按照递增的次序排列增的次序排列, ,则找出最大值和则找出最大值和最小值所需的元最小值所需的元素比较次数为素比较次数为N-N-1,1,这是最佳的情这是最佳的情况。况。 2 2）如果）如果数组中元素按数组中元素按照递减的次序照递减的次序排列，则找出排列，则找出最大值和最小最大值和最小值所需的元素值所需的元素比较次数为比较次数为2(n-1)2(n-1)，这是，这是最坏情况。最坏情况。 3 3）在平）在平均情况下均情况下,A,A中将有一半中将有一半元素使得第元素使得第3 3行的比较为行的比较为真，找出最真，找出最大值和最小大值和最小值所需的元值所需的元素比较次数素比较次数为为3(n-1)/

3、23(n-1)/2。 二、分治算法二、分治算法 1 1、算法思想、算法思想 如果我们将分治策略用于此问题，每次将如果我们将分治策略用于此问题，每次将问题分成大致相等的两部分，分别在这两部分问题分成大致相等的两部分，分别在这两部分中找出最大值与最小值，再将这两个子问题的中找出最大值与最小值，再将这两个子问题的解组合成原问题的解，就可得到该问题的分治解组合成原问题的解，就可得到该问题的分治算法。算法。 2 2、算法描述如下：、算法描述如下：数组只有一个元素数组只有一个元素,即为最大值即为最大值,同时也是最小值。同时也是最小值。第第3行至第行至第8行是数组为二个元素的情况。行是数组为二个元素的情况。

4、第第9行是确定分治段划分行是确定分治段划分3 3、算法说明、算法说明 1)1)第第1 1行，第二行表示数组只有一个元素，即为最行，第二行表示数组只有一个元素，即为最大值，同时也是最小值。大值，同时也是最小值。 2 2）第）第3 3行至第行至第8 8行是当行是当N=2N=2时，即数组为二个元素时，即数组为二个元素的情况。的情况。 3 3）当）当N2N2时时 第第9 9行是确定分治段（划分）。行是确定分治段（划分）。 第第1010、1111行是分治求解（解决）。行是分治求解（解决）。 第第1212、1313行是合并求解（合并）。行是合并求解（合并）。 4、算法分析 1）算法的递归议程 设T(n)表

5、示算法所需的元素比较次数，则可得算法的递归方程为假设假设n n为为2 2的幂，化简的幂，化简T(n)T(n)可得可得 2 2）算法的复杂度）算法的复杂度 这表明算法的最坏、平均以及最好情况的这表明算法的最坏、平均以及最好情况的元素比较次数为元素比较次数为3n/2-23n/2-2。 事实上，至多进行事实上，至多进行3 n/2 3 n/2 次比较是找出最次比较是找出最小值和最大值的充分条件。策略是维持到目前小值和最大值的充分条件。策略是维持到目前为止找到的最小值和最大值。我们并不将每个为止找到的最小值和最大值。我们并不将每个元素与最大值和最小值都进行比较，因为这样元素与最大值和最小值都进行比较，因

6、为这样每个元素需要进行两次比较。下面我们成对处每个元素需要进行两次比较。下面我们成对处理元素。首先，输入元素成对相互进行比较，理元素。首先，输入元素成对相互进行比较，并将较小者与当前最小值比较，较大者与当前并将较小者与当前最小值比较，较大者与当前最大值比较。这样每两个元素进行三次比较。最大值比较。这样每两个元素进行三次比较。 设置当前最小元素和最大元素的初始值，与设置当前最小元素和最大元素的初始值，与N N的奇的奇偶性有关。当规为奇数时，我们将最小值和最大值都设偶性有关。当规为奇数时，我们将最小值和最大值都设为第一个元素，然后，将其余元素成对处理；当为第一个元素，然后，将其余元素成对处理；当N

7、 N为偶为偶数时，我们在前两个元素之间进行一次比较，决定最大数时，我们在前两个元素之间进行一次比较，决定最大值和最小值的初始值，然后，将其余元素成对处理。值和最小值的初始值，然后，将其余元素成对处理。 以下分析上述算法的比较次数。如果以下分析上述算法的比较次数。如果n n为奇数，那为奇数，那么需进行么需进行3 n/2 3 n/2 次比较；如果次比较；如果n n为偶数，我们首先在为偶数，我们首先在前两个元素之间进行一次比较，然后进行前两个元素之间进行一次比较，然后进行3(n-2)/23(n-2)/2次次比较，总共进行比较，总共进行3n/2-23n/2-2次比较。因此，不论在哪一种次比较。因此，不

8、论在哪一种情况下，比较的次数至多为情况下，比较的次数至多为3 n/2 3 n/2 。 设置当前最小元素和最大元素的初始值，与设置当前最小元素和最大元素的初始值，与N N的奇的奇偶性有关。当规为奇数时，我们将最小值和最大值都设偶性有关。当规为奇数时，我们将最小值和最大值都设为第一个元素，然后，将其余元素成对处理；当为第一个元素，然后，将其余元素成对处理；当N N为偶为偶数时，我们在前两个元素之间进行一次比较，决定最大数时，我们在前两个元素之间进行一次比较，决定最大值和最小值的初始值，然后，将其余元素成对处理。值和最小值的初始值，然后，将其余元素成对处理。 以下分析上述算法的比较次数。如果以下分析

9、上述算法的比较次数。如果n n为奇数，那为奇数，那么需进行么需进行3 n/2 3 n/2 次比较；如果次比较；如果n n为偶数，我们首先在为偶数，我们首先在前两个元素之间进行一次比较，然后进行前两个元素之间进行一次比较，然后进行3(n-2)/23(n-2)/2次次比较，总共进行比较，总共进行3n/2-23n/2-2次比较。因此，不论在哪一种次比较。因此，不论在哪一种情况下，比较的次数至多为情况下，比较的次数至多为3 n/2 3 n/2 。 可以证明，任何基于比较的找最大值和最小可以证明，任何基于比较的找最大值和最小值的算法，其元素比较次数下界值的算法，其元素比较次数下界 。在这种意义下，算法在

10、这种意义下，算法REC-MAXMIN是最优的。是最优的。但是但是REC-MAXMIN也有其不足之处，它所要求也有其不足之处，它所要求的存储空间较大，即算法中的每次递归调用都的存储空间较大，即算法中的每次递归调用都需要保留需要保留i，J，fmax，fmin的值及返回地址。的值及返回地址。2.3.2 Strassen矩阵乘法 一、矩阵的乘法 矩阵乘法是科学计算中最基本的问题之一。设A和B是两个nn的矩阵，它们的乘积C=AB也是一个nn的矩阵。其中乘积矩阵中的元素Cij定义为 由此可得，计算矩阵由此可得，计算矩阵C中的每个元素需要中的每个元素需要n次乘法和次乘法和n- 1次加法。因此，计算矩阵次加法

11、。因此，计算矩阵C的的n2个元素所需的时间为个元素所需的时间为O(n3)。二、分治策略 假设n为2的幂，运用分治策略，将矩阵分成4块大小相等的子矩阵，每个子矩阵都其中 如果子矩阵的规模大于如果子矩阵的规模大于2，则可以继续划分这些子，则可以继续划分这些子矩阵，直至每个矩阵变成矩阵，直至每个矩阵变成2 X 2的矩阵。对于的矩阵。对于2 X 2的矩的矩阵的计算，只需阵的计算，只需8次乘法和次乘法和4次加法，计算时间为次加法，计算时间为0(1)。 设设T(n)表示两个表示两个nn矩阵相乘所需的计算时间，则矩阵相乘所需的计算时间，则由由Cijij(C=1,2)的计算可以看出，可将的计算可以看出，可将T

12、(n)的计算转化为的计算转化为计算计算8个个 的矩阵相乘和的矩阵相乘和4个个 矩阵相矩阵相加，而计算加，而计算 4个个 矩阵加法所需时间为矩阵加法所需时间为O(n2)，可得递归方程可得递归方程 该递归方程符合主定理的第一种情形，其解为该递归方程符合主定理的第一种情形，其解为T(n)=O(nT(n)=O(nlb8lb8)=O(n)=O(n3 3) )。因此，直接的分治策略并没有降。因此，直接的分治策略并没有降低算法的计算复杂度。低算法的计算复杂度。19691969年，年，StrassenStrassen经过对问题经过对问题的分析，在分治策略的基础上，通过数学技巧，使算法的分析，在分治策略的基础上

13、，通过数学技巧，使算法的计算复杂度从的计算复杂度从O(nO(n3 3) )降到了降到了O(nO(n2.812.81) )。当此结果第一次。当此结果第一次发表时，震动了数学界。发表时，震动了数学界。 在在Strassen矩阵相乘矩阵相乘(Strassen matrtrix multiplication)算法中算法中,只用了只用了7 个个 的矩阵相乘，但增加了的矩阵相乘，但增加了1 0个矩阵加、减法运算。个矩阵加、减法运算。这这7个矩阵乘法是：个矩阵乘法是： 然后，再通过然后，再通过8 8个矩阵的加、减法运算来计算个矩阵的加、减法运算来计算C Cijij的值的值 在在StrassenStrasse

14、n的分治算法中，用了的分治算法中，用了7 7个的矩阵相乘和个的矩阵相乘和1818个矩阵相加。因此，算法所需的计算时间满足如下个矩阵相加。因此，算法所需的计算时间满足如下递归方程：递归方程： 该递归方程仍然符合主定理的第一种情形，其解为该递归方程仍然符合主定理的第一种情形，其解为 Strassen Strassen矩阵乘法的计算时间较之前面讨矩阵乘法的计算时间较之前面讨论的矩阵乘法有所改进。继论的矩阵乘法有所改进。继StrassenStrassen算法之后，算法之后，许多科研人员致力于该问题的研究，希望对此许多科研人员致力于该问题的研究，希望对此结果有所改进。但结果有所改进。但J JE EHop

15、croftHopcroft和和L LR RKerrKerr已经证明了两个已经证明了两个2 X 22 X 2矩阵相乘必须矩阵相乘必须用用7 7次乘法，因此，要进一步改进矩阵相乘的时次乘法，因此，要进一步改进矩阵相乘的时间复杂度：，就要考虑间复杂度：，就要考虑3 X 33 X 3或或4 X 44 X 4等更大一等更大一级的分块，或者采用新的设计思想。级的分块，或者采用新的设计思想。 2.3.3整数相乘整数相乘 1 1、两个、两个n n位整数相乘位整数相乘(integer multiplica (integer multiplica -tion)-tion)的标准算法所需计算时间为的标准算法所需计算

16、时间为 算法是如此的自然算法是如此的自然, ,以至于我们可能会觉得以至于我们可能会觉得没有更好的算法了。在这里没有更好的算法了。在这里, ,我们却要通过分治我们却要通过分治策略向大家展示一种确实存在的更好的算法。策略向大家展示一种确实存在的更好的算法。 2 2、采用分治法、采用分治法，将，将x x和和y y都分成两部分：都分成两部分：可表示为如下的式子： 假设两个假设两个n/2n/2位的整数相乘不进位位的整数相乘不进位, ,如果按照上式如果按照上式计算计算xyxy的乘积的乘积, ,要做要做4 4次两个次两个n/2n/2位的乘法位的乘法, ,即即acac、adad、bcbc和和adad，此外还要

17、做，此外还要做2 2次移位次移位( (对应于式中的对应于式中的1010n n和和1010n/2n/2) )和和3 3次不超过次不超过2n2n位的整数加法，所有这些移位和加法所位的整数加法，所有这些移位和加法所需计算时间为需计算时间为O(n)O(n)。 3 3、递归方程、递归方程 设设T(n)T(n)表示两个表示两个n n位的整数相乘所需的计算时间位的整数相乘所需的计算时间, ,则则 其中，其中，4T(n/2)4T(n/2)表示需要解表示需要解4 4个规模为个规模为n/2n/2的的子问题，子问题，O(n)O(n)表示利用移位和加法将子问题解表示利用移位和加法将子问题解组合成原问题解的时间。该递归

18、方程符合主定组合成原问题解的时间。该递归方程符合主定理的第一种情形，其解为理的第一种情形，其解为 不幸的是，算法效率仍然没有得到提高。这不幸的是，算法效率仍然没有得到提高。这里的关键是分割产生的里的关键是分割产生的4 4个子问题有些多。个子问题有些多。 4 4、新技巧、新技巧 能否像在能否像在StrassenStrassen算法中所做的那样，通算法中所做的那样，通过一些技巧，或者说通过提高计算的效率，减少过一些技巧，或者说通过提高计算的效率，减少子问题的数量。答案是肯定的。不需分别计算子问题的数量。答案是肯定的。不需分别计算adad和和bcbc，而只需计算它们的和，而只需计算它们的和ad+bc

19、ad+bc。注意下式：。注意下式： (a+b)(c+d)=(ad+bc)+(ac+bd) (a+b)(c+d)=(ad+bc)+(ac+bd) 如果计算出ac,bd和(a+b)(c+d)那么可以从(a+b)(c+d)减去ac,bd，得到ad+bc，即ad+bc= (a+b)(c+d)- ac+bd。当然，增加了一些加法运算，但却使规模为N/2的了问题的乘法减少了一个。递归方程为： 5 5、讨论、讨论 如果要实现这个算法，并不将问题划分至规如果要实现这个算法，并不将问题划分至规模为模为1 1个数字的子问题才停止。由于常规算法利个数字的子问题才停止。由于常规算法利用的加法次数要少，对于规模较小的用

20、的加法次数要少，对于规模较小的n n，常规算，常规算法更有效。因此，我们将问题划分至标准计算机法更有效。因此，我们将问题划分至标准计算机上可解的规模，就可停止划分。上可解的规模，就可停止划分。 6、举例 上述描述的整数相乘算法可用于小数相乘和二进制乘法。我们用下面的例子说明这个方法。设x=3141，y=5927，则 xy中的第一项是将中的第一项是将v的小数点位右移的小数点位右移4位得到的。中间位得到的。中间项是将项是将u-v-w的小数位右移的小数位右移2位得到的。位得到的。 2.3.4 2.3.4 归并排序归并排序 一、步骤一、步骤 归并排序归并排序(merge sorting)(merge

21、sorting)是分治法应用的另一个是分治法应用的另一个实例，由以下三步组成：实例，由以下三步组成： (1)(1)划分：划分：将待排序将待排序n n个元素的序列划分成两个规模个元素的序列划分成两个规模为为n/2n/2的子序列。的子序列。 (2)(2)解决：解决：用归并排序递归地对每一子序列排序。用归并排序递归地对每一子序列排序。 (3)(3)合并：合并：归并两个有序序列，得到排序结果。归并两个有序序列，得到排序结果。 当划分的子序列规模为当划分的子序列规模为1 1时，递归结束。因为一个时，递归结束。因为一个元素的序列被认为是有序的，元素的序列被认为是有序的， 二、归并算法二、归并算法 1 1、

22、算法描述、算法描述 归并排序的关键操作是归并两个已排序的归并排序的关键操作是归并两个已排序的子序列的过程。用过程子序列的过程。用过程MERGE(A,p,q,r)MERGE(A,p,q,r)表示归表示归并两个有序序列并两个有序序列Ap.qAp.q和和Aq+1.rAq+1.r。当过程。当过程MERGE(A,p,q,r)MERGE(A,p,q,r)执行完成后执行完成后Ap.rAp.r中包含的元中包含的元素有序。过程素有序。过程MERGE(A,p,q,r)MERGE(A,p,q,r)描述如下：描述如下： 第第1 1行计算子数组行计算子数组Ap.qAp.q的大小的大小 第第2 2行计算子数组行计算子数组

23、Aq+1.rAq+1.r的大小的大小第第4,54,5行用行用forfor循环拷贝子数组循环拷贝子数组L L第第6,76,7行用行用forfor循环拷贝子数组循环拷贝子数组R R在数组在数组L L和和R R的尾部设置观察哨的尾部设置观察哨给i赋初值给j赋初值2、示例、示例 调用调用MERGE(A,9,12,16)MERGE(A,9,12,16)时时, ,子数组包含序列子数组包含序列(2,4(2,4，5 5，7,1,2,3,6)7,1,2,3,6)。执行完第。执行完第4 49 9行后行后, ,数组数组L L的值为的值为(2(2，4,5,7,)4,5,7,)，数组，数组R R的值为的值为(1,2,3

24、,6,)(1,2,3,6,)。A A中浅色阴影中浅色阴影部分包含最终值部分包含最终值,L,L和和R R中浅色阴影部分表示必须被拷贝中浅色阴影部分表示必须被拷贝到到A A中的值。浅色阴影部分包含了原始数组中的值。浅色阴影部分包含了原始数组A9.16A9.16中中的值。的值。A A中深色阴影部分包含已被拷贝完的值中深色阴影部分包含已被拷贝完的值,L,L和和R R中中深色阴影部分表示已被拷贝到深色阴影部分表示已被拷贝到A A中的值。中的值。 在图在图2-82-8的的(a)(a)(h)(h)中，中，k k、i i、j j分别表示数组分别表示数组A A、L L和和R R在第在第12-1712-17行循环

25、开始前的下标。图行循环开始前的下标。图2-8(i)2-8(i)是最终是最终结果，此时子数组结果，此时子数组A9.16A9.16有序。两个观察哨是有序。两个观察哨是L L和和R R数组中的惟一没被拷贝到数组中的惟一没被拷贝到A A中的元素。中的元素。3 3、证明、证明 现在需要证明，现在需要证明，在第在第12121717行的行的forfor循环开始执行之前，循环开始执行之前，这个循环不变式成立，这个循环不变式成立，并在循环的每次迭代并在循环的每次迭代过程中，循环不变式过程中，循环不变式保持。当循环终止时，保持。当循环终止时，循环不变式还可以提循环不变式还可以提供证明算法正确性的供证明算法正确性的

26、有用性质。有用性质。 初始初始: :在循环的在循环的第一次迭代前第一次迭代前,k=p,k=p,子数组子数组Ap.k-1Ap.k-1为为空。空数组包含空。空数组包含k-k-p=0p=0个个L L和和R R中的最小中的最小元素。由于元素。由于i=j=1i=j=1，因此因此LiLi和，和，RjRj分别是各自数组中分别是各自数组中还未拷贝到还未拷贝到A A中的最中的最小元素。小元素。 维持维持: :为证明每次迭为证明每次迭代过程维持不变式代过程维持不变式, ,我们首我们首先假定先假定LiRiLiRi。LiLi是是没有拷贝到没有拷贝到A A中的最小元素。中的最小元素。因为因为Ap.k-1Ap.k-1包含

27、包含k-pk-p个最个最小元素小元素, ,在执行第在执行第1414行后行后, , LiLi被拷贝到被拷贝到Ak,Ak,子数组子数组Ap.kAp.k包含是包含是k-p+1k-p+1个最小个最小元素。元素。 在在forfor循环更新中循环更新中k k增加增加, ,执行第执行第1515行时行时i i增加增加, ,重新建重新建立下一次迭代的循环不变式。立下一次迭代的循环不变式。如果如果LiRj,LiRj,那么第那么第16161717行执行维持循环不变式的行执行维持循环不变式的相应行为。相应行为。 4、运行时间、运行时间 三、归并排序算法三、归并排序算法 1 1、算法描述、算法描述 我们将利用我们将利用

28、MERGEMERGE作为排序算法的子过程，作为排序算法的子过程，利用利用MERGE-SORTMERGE-SORT对子数组对子数组Ap.rAp.r中的元素进行中的元素进行排序。排序。 如果如果prpr，则子数组至多有一个元素，因而，则子数组至多有一个元素，因而有序；否则第有序；否则第2 2行计算下标行计算下标q q，将数组，将数组Ap.rAp.r划划分成两个子数组分成两个子数组Ap.qAp.q和和Aq+1.rAq+1.r，它们分，它们分别包含别包含 算法通过两个长为算法通过两个长为1 1的子序列形成长为的子序列形成长为2 2的的有序序列，再通过两个长为有序序列，再通过两个长为2 2的有序序列形成的有序序列形成长为长为4 4的有序序列，直到通过两个长为的有序序列，直