第四章3算法策略

1、4.3 分而治之算法分而治之算法 431 分治算法框架分治算法框架 432 典型二分法典型二分法 433 二分法不相似情况二分法不相似情况 434 二分法不独立情况二分法不独立情况 435 非等分分治非等分分治431 分治算法框架分治算法框架 1算法设计思想算法设计思想分治法求解问题的过程是，将整个问题分解成若干个小问题后分分治法求解问题的过程是，将整个问题分解成若干个小问题后分而治之。如果分解得到的子问题相对来说还太大，则可反复使用而治之。如果分解得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出方分治策略将这些子问题分成更小的同类型子问题，直至产

2、生出方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。题的解。分治法的基本步骤在每一层递归上都有三个步骤：分治法的基本步骤在每一层递归上都有三个步骤：1）分解：将原问题分解为若干个规模较小，相互独立，与原问）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；题形式相同的子问题； 2）解决：若子问题规模较小而容易被解决则直接解，否则再）解决：若子问题规模较小而容易被解决则直接解，否则再继续分解为更小的子问题，直到容易解决；继续分解为更小的子问题，直到容易解决； 3）合并：将已求解的各个子问题的解，逐步合

3、并为原问题的）合并：将已求解的各个子问题的解，逐步合并为原问题的解。解。有时问题分解后，不必求解所有的子问题，也就不必作第三步有时问题分解后，不必求解所有的子问题，也就不必作第三步的操作。比如折半查找，在判别出问题的解在某一个子问题中的操作。比如折半查找，在判别出问题的解在某一个子问题中后，其它的子问题就不必求解了，问题的解就是最后（最小）后，其它的子问题就不必求解了，问题的解就是最后（最小）的子问题的解。分治法的这类应用，又称为的子问题的解。分治法的这类应用，又称为“减治法减治法”。 多数问题需要所有子问题的解，并由子问题的解，使用恰多数问题需要所有子问题的解，并由子问题的解，使用恰当的方法

4、合并成为整个问题的解，比如合并排序，就是不断将当的方法合并成为整个问题的解，比如合并排序，就是不断将子问题中已排好序的解合并成较大规模的有序子集。子问题中已排好序的解合并成较大规模的有序子集。 2适合用分治法策略的问题适合用分治法策略的问题当求解一个输入规模为当求解一个输入规模为n且取值又相当大的问题时，用蛮力策且取值又相当大的问题时，用蛮力策略效率一般得不到保证。若问题能满足以下几个条件，就能用分略效率一般得不到保证。若问题能满足以下几个条件，就能用分治法来提高解决问题的效率。治法来提高解决问题的效率。1） 能将这能将这n个数据分解成个数据分解成k个不同子集合，且得到个不同子集合，且得到k个

5、子集合个子集合是可以独立求解的子问题，其中是可以独立求解的子问题，其中1kn；2） 分解所得到的子问题与原问题具有相似的结构，便于利分解所得到的子问题与原问题具有相似的结构，便于利用递归或循环机制；用递归或循环机制；在求出这些子问题的解之后，就可以推解出原问题的解；在求出这些子问题的解之后，就可以推解出原问题的解； 分治法的一般的算法设计模式如下：分治法的一般的算法设计模式如下：Divide-and-Conquer(int n) /nDivide-and-Conquer(int n) /n为问题规模为问题规模/ / if if （nn0nn0） /n0 /n0 为可解子问题的规模为可解子问题的

6、规模/ / 解子问题；解子问题； return(return(子问题的解子问题的解) )； for for （i=1 ;i=k;i+i=1 ;i=k;i+） / /分解为较小子问题分解为较小子问题p1,p2,pk/p1,p2,pk/ yi=Divide-and-Conquer(|Pi|); / yi=Divide-and-Conquer(|Pi|); /递归解决递归解决Pi/Pi/ T =MERGE(y1,y2,.,yk); / T =MERGE(y1,y2,.,yk); /合并子问题合并子问题/ / return(T); return(T); 其中其中|P|P|表示问题表示问题P P的规模；

7、的规模；n0n0为一阈值，表示当问题为一阈值，表示当问题P P的规的规模不超过模不超过n0n0时，问题已容易直接解出，不必再继续分解。算法时，问题已容易直接解出，不必再继续分解。算法MERGE(y1,y2,.,yk)MERGE(y1,y2,.,yk)是该分治法中的合并子算法，用于将是该分治法中的合并子算法，用于将P P的的子问题子问题P1 ,P2 ,.,PkP1 ,P2 ,.,Pk的相应的解的相应的解y1,y2,.,yky1,y2,.,yk合并为合并为P P的解。的解。在一些问题中不需要这一步。如析半查找、在一些问题中不需要这一步。如析半查找、4 43 32 2中的例中的例1 1、例、例2 2

8、等。等。432 典型典型二分法二分法 不同于现实中对问题（或工作）的分解，可能会考虑问题不同于现实中对问题（或工作）的分解，可能会考虑问题（或工作）的重点、难点、承担人员的能力等来进行问题的分（或工作）的重点、难点、承担人员的能力等来进行问题的分解和分配。在算法设计中每次一个问题分解成的子问题个数一解和分配。在算法设计中每次一个问题分解成的子问题个数一般是固定的，每个子问题的规模也是平均分配的。当每次都将般是固定的，每个子问题的规模也是平均分配的。当每次都将问题分解为原问题规模的一半时，称为二分法。二分法是分治问题分解为原问题规模的一半时，称为二分法。二分法是分治法较常用的分解策略，数据结构课

9、程中的折半查找、归并排序法较常用的分解策略，数据结构课程中的折半查找、归并排序等算法都是采用此策略实现的。等算法都是采用此策略实现的。【例【例1 1】金块问题：】金块问题： 老板有一袋金块老板有一袋金块( (共共n n块块) )，最优秀的雇员得，最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。金块。算法设计算法设计1 1：比较简单的方法是逐个的进行比较查找。先拿两块比较简单的方法是逐个的进行比较查找。先拿两块

10、比较重量，留下重的一个与下一块比较，直到全部比较完毕，比较重量，留下重的一个与下一块比较，直到全部比较完毕，就找到了最重的金子。算法类似于一趟选择排序，算法如下：就找到了最重的金子。算法类似于一趟选择排序，算法如下： maxmin( float a,int n)maxmin( float a,int n) max=min=a1; max=min=a1; for(i=2 i=n i+ ) for(i=2 i=n i+ ) if(max ai) max=ai; if(max ai) min=ai; else if(min ai) min=ai; float an;float an;maxmin （

11、int i, int j ,float &fmax, float &fminint i, int j ,float &fmax, float &fmin）int mid; float lmax, lmin, rmax, rmin;int mid; float lmax, lmin, rmax, rmin;if (i=j) fmax= ai; fmin=ai;if (i=j) fmax= ai; fmin=ai;else if (i=j-1)else if (i=j-1) if(aiaj) fmax=aj if(airmax) fmax=lmax; if(lmax

12、rmax) fmax=lmax; else fmax=rmax; else fmax=rmax; if(lminrmin) fmin=rmin; if(lminrmin) fmin=rmin; else fmin=lmin; else fmin=lmin; 算法分析：算法分析：MAXMINMAXMIN需要的元素比较数是多少呢？如果用需要的元素比较数是多少呢？如果用T(n)T(n)表示这个数，则所导出的递归关系式是表示这个数，则所导出的递归关系式是: :当当n n是是2 2的幂时，即对于这个某个正整数的幂时，即对于这个某个正整数k，n=2k，有，有 【例【例2 2】残缺棋盘残缺棋盘残缺棋盘是一个

13、有残缺棋盘是一个有2 2k k2 2k k （k1k1）个）个方格的棋盘，其中恰有方格的棋盘，其中恰有一个方格残缺。图一个方格残缺。图4-7给出给出k=1时各种可能的残缺棋盘，其时各种可能的残缺棋盘，其中残缺的方格用阴影表示。中残缺的方格用阴影表示。 号 号 号 号图4-7 四种三格板这样的棋盘我们称作这样的棋盘我们称作“三格板三格板”，残缺棋盘问题就是要用这，残缺棋盘问题就是要用这四种三格板覆盖更大的残缺棋盘。在此覆盖中要求：四种三格板覆盖更大的残缺棋盘。在此覆盖中要求：1 1）两个三格板不能重叠）两个三格板不能重叠2 2）三格板不能覆盖残缺方格，但必须覆盖其他所有的方格）三格板不能覆盖残缺

14、方格，但必须覆盖其他所有的方格在这种限制条件下，所需要的三格板总数为在这种限制条件下，所需要的三格板总数为(2k2k -1 )/3。 433 二分法不相似情况算法设计算法设计1 1：下面用分而治之方法解决残缺棋盘问题。下面用分而治之方法解决残缺棋盘问题。1 1）问题分解过程如下：）问题分解过程如下：以以k=2时的问题为例，用二分法进行分解，得到的是如下图时的问题为例，用二分法进行分解，得到的是如下图4-8，用双线划分的四个，用双线划分的四个k=1的棋盘。但要注意这四个棋盘，并的棋盘。但要注意这四个棋盘，并不都是与原问题相似且独立的子问题。因为当如图不都是与原问题相似且独立的子问题。因为当如图4

15、-8中的中的残缺方格在左上部时，第残缺方格在左上部时，第1个子问题与原问题相似，而右上个子问题与原问题相似，而右上角、左下角和右下角三个子棋盘（也就是图中标识为角、左下角和右下角三个子棋盘（也就是图中标识为2、3、4号子棋盘），并不是原问题的相似子问题，自然也就不能号子棋盘），并不是原问题的相似子问题，自然也就不能独立求解了。当使用一个独立求解了。当使用一个号三格板（图中阴影）覆盖号三格板（图中阴影）覆盖2、3、4号三个子棋盘的各一个方格后，如号三个子棋盘的各一个方格后，如4-8右图所示，我们把覆右图所示，我们把覆盖后的方格，也看作是残缺方格（称为盖后的方格，也看作是残缺方格（称为“伪伪”残缺

16、方格），残缺方格），这时的这时的2、3、4号子问题就是独立且与原问题相似的子问题号子问题就是独立且与原问题相似的子问题了。了。 从以上例子还可以发现，当残缺方格在第从以上例子还可以发现，当残缺方格在第1个子棋盘，用个子棋盘，用号三号三格板覆盖其余三个子棋盘的交界方格，可以使另外三个子棋格板覆盖其余三个子棋盘的交界方格，可以使另外三个子棋盘转化为独立子问题；同样地（如下图盘转化为独立子问题；同样地（如下图4-9所示），当残缺方所示），当残缺方格在第格在第2个子棋盘时，则首先用个子棋盘时，则首先用号三格板进行棋盘覆盖，当号三格板进行棋盘覆盖，当残缺方格在第残缺方格在第3个子棋盘时，则首先用个子棋盘

17、时，则首先用号三格板进行棋盘覆号三格板进行棋盘覆盖，当残缺方格在第盖，当残缺方格在第4个子棋盘时，则首先用个子棋盘时，则首先用号三格板进行号三格板进行棋盘覆盖，这样就使另外三个子棋盘转化为独立子问题。棋盘覆盖，这样就使另外三个子棋盘转化为独立子问题。如下图如下图4-94-9：同样地同样地k=1，2，3，4都是如此，都是如此，k=1为停止条件。为停止条件。图图4-9 4-9 其它其它4 4* *4 4的残缺棋盘的残缺棋盘2 2）棋盘的识别）棋盘的识别 棋盘的规模是一个必要的信息，有了这个信息，只要知道其左上棋盘的规模是一个必要的信息，有了这个信息，只要知道其左上角的左上角方格所在行、列就可以唯一

18、确定一个棋盘了，残角的左上角方格所在行、列就可以唯一确定一个棋盘了，残缺方格或缺方格或“伪伪”残缺方格直接用行、列号记录。残缺方格直接用行、列号记录。 tr tr 棋盘中左上角方格所在行。棋盘中左上角方格所在行。 tc tc 棋盘中左上角方格所在列。棋盘中左上角方格所在列。 dr dr 残缺方块所在行。残缺方块所在行。 dl dl 残缺方块所在列。残缺方块所在列。 size size 棋盘的行数或列数。棋盘的行数或列数。数据结构设计：数据结构设计：用二维数组用二维数组board board ，模拟棋盘。覆盖，模拟棋盘。覆盖残缺棋盘所需要的三格板数目为：残缺棋盘所需要的三格板数目为：( size

19、( size2 2 -1 ) / 3 -1 ) / 3将这些三格板编号为将这些三格板编号为1 1到到( s i z e( s i z e2 2-1 ) / 3-1 ) / 3。则将残缺棋。则将残缺棋盘三格板编号的存储在数组盘三格板编号的存储在数组board board 的对应位置中，这的对应位置中，这样输出数组内容就是问题的解。结合图样输出数组内容就是问题的解。结合图4-94-9，理解算法。，理解算法。算法如下：算法如下： int amount=0; main（）（） int size=1,x,y; input(k); for (i=1;i=k;i+) size=size*2; print(“

20、input incomplete pane ”); input(x,y); Cover(0, 0, x, y, size); 图图4-9 一个一个4*4的残缺棋盘及其解的残缺棋盘及其解 Cover(int tr, int tc, int dr, int dc, int size) if (size2) return;int t = amount +, / 所使用的三格板的数目所使用的三格板的数目s=size/2; / 子问题棋盘大小子问题棋盘大小 if (dr tr + s & dc tc + s) / /残缺方格位于左上棋盘残缺方格位于左上棋盘Cover ( tr, tc, dr,

21、dc, s); Boardtr + s - 1tc + s = t; / 覆盖号三格板覆盖号三格板 Boardtr + stc + s - 1 = t; Boardtr + stc + s = t; Cover (tr, tc+s, tr+s-1, tc+s, s); / 覆盖其余部分覆盖其余部分 Cover(tr+s, tc, tr+s, tc+s-1, s); Cover(tr+s, tc+s, tr+s, tc+s, s); else if(dr = tc + s) /残缺方格位于右上象限残缺方格位于右上象限 Cover ( t r, tc+s, dr, dc, s); Boardtr

22、+ s - 1tc + s - 1 = t; / 覆盖号三格板覆盖号三格板 Boardtr + stc + s - 1 = t; Boardtr + stc + s = t; Cover (tr, tc, tr+s-1, tc+s-1, s); /覆盖其余部分覆盖其余部分 Cover(tr+s, tc, tr+s, tc+s-1, s); Cover(tr+s, tc+s, tr+s, tc+s, s); else if (dr = tr + s & dc = tr + s & dc = tc + s)/ 残缺方格位于右下象限残缺方格位于右下象限 Cover(tr+s, tc+

23、s, dr, dc, s); Boardtr + s - 1tc + s - 1 = t; / 覆盖号三格板覆盖号三格板 Boardtr + s - 1tc + s = t; Boardtr + stc + s - 1 = t; Cover (tr, tc, tr+s-1, tc+s-1, s); /覆盖其余部分覆盖其余部分 Cover (tr, tc+s, tr+s-1, tc+s, s); Cover(tr+s, tc, tr+s, tc+s-1, s); void OutputBoard(int size) for (int i = 0; i size; i+) for (int j =

24、 0; j 0) return(aleft) ; else return(0);else center=(left+right)/2; left_sum=max_sub_sum(a,left,center); right_sum=max_sub_sum(a,center+1,right); s1=0; /处理情形处理情形3/ lefts=0;for (i=center;i=left;i-) lefts=lefts+ai; if( leftss1) s1=lefts;s2=0; rights=0;for( i=center+1;is2) s2=rights;if (s1+s2left_sum a

25、nd right_sumleft_sum) rturn(left_sum);if (s1+s2right_sum) return(right_sum); return(s1+s2); 【例【例4 4】大整数乘法大整数乘法在某些情况下，我们需要处理很大的整数，它无法在计算机在某些情况下，我们需要处理很大的整数，它无法在计算机硬件能直接允许的范围内进行表示和处理。若用浮点数来存硬件能直接允许的范围内进行表示和处理。若用浮点数来存储它，只能近似地参与计算，计算结果的有效数字会受到限储它，只能近似地参与计算，计算结果的有效数字会受到限制。若要精确地表示大整数，并在计算结果中要求精确地得制。若要精确地表

26、示大整数，并在计算结果中要求精确地得到所有位数上的数字，就必须用软件的方法来实现大整数的到所有位数上的数字，就必须用软件的方法来实现大整数的算术运算。请设计一个有效的算法，可以进行两个算术运算。请设计一个有效的算法，可以进行两个n位大整数位大整数的乘法运算。的乘法运算。数据结构设计数据结构设计：首先用数组存储大整数数据，再将两个乘数：首先用数组存储大整数数据，再将两个乘数和积都按由低位到高位逐位存储到数组元素中。和积都按由低位到高位逐位存储到数组元素中。算法设计算法设计1 1：存储好两个高精度数据后，模拟竖式乘法，让两：存储好两个高精度数据后，模拟竖式乘法，让两个高精度数据的按位交叉相乘，并逐

27、步累加即可得到精确的个高精度数据的按位交叉相乘，并逐步累加即可得到精确的结果，用二重循环就可实现。结果，用二重循环就可实现。 算法设计算法设计1：存储好两个高精度数据后，我们模拟竖式乘法，存储好两个高精度数据后，我们模拟竖式乘法，让两个高精度数据的按位交叉相乘，并逐步累加，即可得到精让两个高精度数据的按位交叉相乘，并逐步累加，即可得到精确的计算结果。用二重循环就可控制两个数不同位相乘的过程。确的计算结果。用二重循环就可控制两个数不同位相乘的过程。只考虑正整数的乘法，算法细节设计如下：只考虑正整数的乘法，算法细节设计如下：1) 对于大整数比较方便的输入方法是，按字符型处理，存储在对于大整数比较方

28、便的输入方法是，按字符型处理，存储在字符串数组字符串数组s1、s2中，计算结果存储在整型数组中，计算结果存储在整型数组a中。中。2)2)通过字符的通过字符的ASCII码，数字字符可以直接参与运算，码，数字字符可以直接参与运算，k位数位数字与字与j位数字相乘的表达式为：位数字相乘的表达式为：s1k-48)*(s2j-48)。这是这是C语言的处理方法，其它程序设计语言有对应的函可以实语言的处理方法，其它程序设计语言有对应的函可以实现数字字符与数字的转换，这里不详细介绍了。现数字字符与数字的转换，这里不详细介绍了。3)3)每一次数字相乘的结果位数是不固定的，而结果数组中每个每一次数字相乘的结果位数是

29、不固定的，而结果数组中每个元素只存储一位数字，所以用变量元素只存储一位数字，所以用变量b暂存结果，若超过暂存结果，若超过1位数则位数则进位，用变量进位，用变量d存储。这样每次计算的表达式为：存储。这样每次计算的表达式为： b= ai+(s1k-48)*(s2j-48)+d;。main( )main( ) long b,c,d; int i,i1,i2,j,k,n,n1,n2,a256; long b,c,d; int i,i1,i2,j,k,n,n1,n2,a256; char s1256,s2256; char s1256,s2256; input(s1); input(s2); input

30、(s1); input(s2); for (i=0;i255;i+) ai=0; for (i=0;i255;i+) ai=0; n1=strlen(s1); n2=strlen(s2); d=0; n1=strlen(s1); n2=strlen(s2); d=0; for (i1=0,k=n1-1;i1n1;i1+,k-) for (i1=0,k=n1-1;i1n1;i1+,k-) for (i2=0,j=n2-1;i2n2;i2+,j-) for (i2=0,j=n2-1;i20) while (d0) i=i+1; ai= ai+d mod 10; d=d/10; i=i+1; ai=

31、 ai+d mod 10; d=d/10; n=i; n=i; for (i=n;i=0;i-) print(ai); for (i=n;i=0;i-) print(ai); 算法说明：算法说明：循环变量循环变量j j、k k分别是两个乘数字符串的下标。分别是两个乘数字符串的下标。i1i1表示字符串表示字符串str1str1由低位到高位的位数，范围由低位到高位的位数，范围0n1-10n1-1（与（与k k相相同）。同）。i2i2表示字符串表示字符串str2str2由低位到高位的位数，范围由低位到高位的位数，范围0n2-0n2-1 1（与（与j j相同）。相同）。i i表示乘法正在运算的位，也是

32、计算结果存储表示乘法正在运算的位，也是计算结果存储的位置。的位置。算法分析算法分析1 1：算法是以算法是以n1,n2n1,n2代表两个乘数的位数，由算法中的循代表两个乘数的位数，由算法中的循环嵌套知，算法的主要操作是乘法，算法的时间复杂度是环嵌套知，算法的主要操作是乘法，算法的时间复杂度是O O（n1n1* *n2n2）。）。 算法设计算法设计2 2：下面们用分治法来设计一个更有效的大整数乘积算下面们用分治法来设计一个更有效的大整数乘积算法。设计的重点是要提高乘法算法的效率，设计如下：法。设计的重点是要提高乘法算法的效率，设计如下：设设X和和Y都是都是n位的二进制整数，现在要计算它们的乘积位的

33、二进制整数，现在要计算它们的乘积X*Y。图图4-10 4-10 大整数大整数X X和和Y Y的分段的分段 将将n n位的二进制整数位的二进制整数X X和和Y Y各分为各分为2 2段，每段的长为段，每段的长为n/2n/2位位( (为简为简单起见，假设单起见，假设n n是是2 2的幂的幂) )，如图，如图4-104-10所示。显然问题的答案并不所示。显然问题的答案并不是是A A* *C C* *K1+CK1+C* *D D* *K2K2（K1K1、K2K2与与A A、B B、C C、D D无关），也就是说，这无关），也就是说，这样做并没有将问题分解成两个独立的子问题。按照乘法分配律，样做并没有将问

34、题分解成两个独立的子问题。按照乘法分配律，分解后的计算过程如下：分解后的计算过程如下：记：记：X=AX=A* *2 2n/2n/2+B +B ，Y=CY=C* *2 2n/2n/2+D+D。这样，。这样，X X和和Y Y的乘积为：的乘积为：X*Y=(A*2n/2+B)(C*2n/2+D)=A*C*2n+(AD+CB)*2n/2+B*D (1)(1)模型分析模型分析：如果按式如果按式(1)(1)计算计算X X* *Y Y，则我们必须进行，则我们必须进行4 4次次n/2n/2位整数的乘法位整数的乘法(AC(AC，ADAD，BCBC和和BD)BD)，以及以及3 3次不超过次不超过n n位的整数加法，

35、此外还要做位的整数加法，此外还要做2 2次移位次移位 ( (分别对应于式分别对应于式(1)(1)中乘中乘2 2n n和乘和乘2 2n/2n/2) )。所有这些加法和移。所有这些加法和移位共用位共用O(n)O(n)步运算。设步运算。设T(n)T(n)是是2 2个个n n位整数相乘所需的运算总数，位整数相乘所需的运算总数，则由式则由式(1)(1)，我们有以下，我们有以下(2)(2)式：式： T T（1 1）=1=1 T T（n n）=4T(n/2)+O(n) =4T(n/2)+O(n) （2 2） 由此递归式迭代过程如下：由此递归式迭代过程如下：T(n)=4T(n/2)+cnT(n)=4T(n/2

36、)+cn =4(4T(n/4)+cn/2)+cn =4(4T(n/4)+cn/2)+cn =16(T(n/8)+ cn/4)+3cn/2+cn = =16(T(n/8)+ cn/4)+3cn/2+cn = = = +4+4k-1 k-1 * *2c+42c+4k-2 k-2 * *4c+4c24c+4c2k-1k-1+c2+c2k k =O =O（4 4k k）= O= O(nlog4) =O =O（n n2 2）所以可得算法的时间复杂度为所以可得算法的时间复杂度为T(n)=O(nT(n)=O(n2 2) )。模型改进：模型改进：可以把可以把X X* *Y Y写成另一种形式：写成另一种形式：X

37、 X* *Y=AY=A* *C C* *2 2n n+(A-B)(D-C)+AC+BD+(A-B)(D-C)+AC+BD* *2 2n/2n/2+B+B* *D D (3) (3)式式(3)(3)看起来比式看起来比式(1)(1)复杂，但它仅需做复杂，但它仅需做3 3次次n/2n/2位整数的乘法：位整数的乘法：ACAC，BDBD和和(A-B)(D-C)(A-B)(D-C)，6 6次加、减法和次加、减法和2 2次移位。由此可得次移位。由此可得: : (4) (4)用解递归方程的迭代公式法，不妨设用解递归方程的迭代公式法，不妨设n=2n=2k k： T(n)=3T(n/2)+cnT(n)=3T(n/

38、2)+cn =3(3T(n/4)+cn/2)+cn =3(3T(n/4)+cn/2)+cn =9(T(n/8)+ cn/4)+3cn/2+cn =9(T(n/8)+ cn/4)+3cn/2+cn = = = =3 3k k +3+3k-1 k-1 * *2c+32c+3k-2 k-2 * *4c+3c24c+3c2k-1k-1+c2+c2k k = O = O(nlog3)则得到则得到T(n)=OT(n)=O(nlog3)=O(nO(n1.59) )。MULT(X,Y,n) X和和Y为为2个小于个小于2n的整数，返回结果为的整数，返回结果为X和和Y的乘积的乘积XY S=SIGN(X)*SIGN

39、(Y); /S为为X和和Y的符号乘积的符号乘积 X=ABS(X); Y=ABS(Y); /X和和Y分别取绝对值分别取绝对值 if（ n=1） if (X=1 and Y=1) return(S)； else return(0)； else A=X的左边的左边n/2位位; B=X的右边的右边n/2位位; C=Y的左边的左边n/2位位; D=Y的右边的右边n/2位位; ml=MULT(A,C,n/2); m2=MULT(A-B,D-C,n/2); m3=MULT(B,D,n/2); S=S*(m1*2n+(m1+m2+m3)*2n/2+m3); return(S); 435 非等分分治非等分分治

40、以上的例子都是用二分策略把问题分解为与原问题相似以上的例子都是用二分策略把问题分解为与原问题相似“相等相等”的子问题。下面看几个用的子问题。下面看几个用“非等分二分法非等分二分法”解决问题的例子。解决问题的例子。选择问题就是选择问题就是“从一组数中选择的第从一组数中选择的第k小的数据小的数据”，这个问题的，这个问题的一个应用就是寻找中值元素，此时一个应用就是寻找中值元素，此时k = n / 2 。中值是一个很。中值是一个很有用的统计量，例如中间工资，中间年龄，中间重量等。有用的统计量，例如中间工资，中间年龄，中间重量等。k取其他取其他值也是有意义的，例如，通过寻找第值也是有意义的，例如，通过寻

41、找第k=n/2 、k=n/3和和 k=n/4的的年龄年龄,可将人口进行划分，了解人口的分布情况。可将人口进行划分，了解人口的分布情况。 这个问题可以通过排序来解决，但根据这个问题可以通过排序来解决，但根据数据数据结构结构课程的经验，最好的排序算法的复杂性也是课程的经验，最好的排序算法的复杂性也是O（n*log(n)），下面我们要利用分治法，找到复杂），下面我们要利用分治法，找到复杂性为性为O（n）的算法。但这个问题不能用简单的二分）的算法。但这个问题不能用简单的二分法分解成完全独立、相似的两个子问题。因为在选法分解成完全独立、相似的两个子问题。因为在选出分解后第一组的第出分解后第一组的第k小的

42、数据和第二组的第小的数据和第二组的第k小的小的数据，不能保证在这两个数据之一是原问题的解。数据，不能保证在这两个数据之一是原问题的解。以求一组数的第二小的数据为例，我们讨论解决问题的办法。以求一组数的第二小的数据为例，我们讨论解决问题的办法。【例【例5】选择问题】选择问题1 求一组数的第二小的数。求一组数的第二小的数。 float a100;main( ) int n; float min2; input(n); for (i=0;in-1;i=i+1) input(ai);min2=second(n);print(min2); second（int n） float min2,min1; t

43、wo(0,n-1, min2, min1); return min2;two（int i, int j，float &fmin2, float &fmin1） float lmin2,lmin1,rmin2,rmin1; int mid; if （i=j） fmin2=fmin1=ai else if (i=j-1) if(aiaj) fmin2=aj；fmin1=ai; else fmin2=ai; fmin1=aj; else mid=(i+j)/2; two（i，mid，lmin2，lmin1）; two（mid+1，j，rmin2，rmin1）; if (lmin1rmin1) if (lmin2rmin1) fmin1=lmin1;fmin2=lmin2; else fmin1=lmin1; fmin2=rmin1; else if ( rmin2k-1nleftk-1，则选择问题的答案继续在左子集中找，问，则选择问题的答案继续在左子集中找，问 题规模变小了。题规模变小了。 3 3） nleftk-1nleftk-1，则选择问题的答案继续在右子集中找，问，则选择问题的