第四章分治算法 §1.算法基本思想 考虑下面折半搜索算法 程序4-1-1折半搜索 template<class T, int BinarySearch(t al, const T& x, int n W/在数组a[0:n-1]中搜索x,数组中的元素满足a[0]<=a[1] ·<≡a[n-1]。如果找到x,则返回所在位置(数组元素的下标) //否则返回-1 int left=0; int right=n-1 while(left(=right)( int middle=(left+right)/2 if(x==amiddle]) return middle if(x)a middled) left=middle+1 else right=middle -1 return-1;//未找到x while的每次循环(最后一次除外)都将以减半的比例缩小搜索范围,所以, 该循环在最坏的情况下需要执行θ(logn)次。由于每次循环需耗时⊙(1),因此在 最坏情况下,总的时间复杂性为e(logn) 折半搜索算法贯彻一个思想,即分治法。当人们要解决一个输入规模,比 如n,很大的问题时,往往会想到将该问题分解。比如将这n个输入分成k个不 同的子集。如果能得到k个不同的可独立求解的子问题,而且在求出这些子问题 的解之后,还可以找到适当的方法把它们的解合并成整个问题的解,那么复杂的 难以解决的问题就可以得到解决。这种将整个问题分解成若干个小问题来处理的 方法称为分治法。一般来说,被分解出来的子问题应与原问题具有相同的类型, 这样便于采用递归算法。如果得到的子问题相对来说还较大,则再用分治法,直 到产生出不用再分解就可求解的子问题为止。人们考虑和使用较多的是k=2的情
第四章 分 治 算 法 §1. 算法基本思想 考虑下面折半搜索算法 程序 4-1-1 折半搜索 template<class T> int BinarySearch(T a[], const T& x, int n) {// 在 数 组 a[0:n-1] 中 搜 索 x ， 数 组 中 的 元 素 满 足 a[0]<=a[1] //<= ···<=a[n-1]。如果找到 x，则返回所在位置（数组元素的下标）， //否则返回 –1 int left=0; int right=n-1; while(left<=right){ int middle=(left+right)/2; if(x==a[middle]) return middle; if(x>a[middle]) left=middle+1; else right=middle – 1; } return –1; //未找到 x } while 的每次循环（最后一次除外）都将以减半的比例缩小搜索范围，所以， 该循环在最坏的情况下需要执行Θ(log n)次。由于每次循环需耗时Θ(1) ，因此在 最坏情况下，总的时间复杂性为Θ(log n)。 折半搜索算法贯彻一个思想，即分治法。当人们要解决一个输入规模，比 如 n，很大的问题时，往往会想到将该问题分解。比如将这 n 个输入分成 k 个不 同的子集。如果能得到 k 个不同的可独立求解的子问题，而且在求出这些子问题 的解之后，还可以找到适当的方法把它们的解合并成整个问题的解，那么复杂的 难以解决的问题就可以得到解决。这种将整个问题分解成若干个小问题来处理的 方法称为分治法。一般来说，被分解出来的子问题应与原问题具有相同的类型， 这样便于采用递归算法。如果得到的子问题相对来说还较大，则再用分治法，直 到产生出不用再分解就可求解的子问题为止。人们考虑和使用较多的是 k=2 的情
形,即将整个问题二分。以下用A[l:n来表示n个输入,用DanC(p,q)表示处理 输入为A[p:q]情况的问题。 分治法控制流程 DanC(p, g) globa1n,A[l:n]; integer m,p,q;//1sp≤q≤n if Small(p, g) then return G(p, g) else m=Divide(p, g);// p<m<q return Combine(DanC (p, m), DanC (m+1, g)) endif end danC 这里,Smal1l(p,q)是一个布尔值函数,用以判断输入规模为q-p+1的问题 是否小到无需进一步细分即可容易求解。若是,则调用能直接计算此规模下子问 题解的函数G(p,q).而 Divide(p,q)是分割函数,决定分割点, Combine(x,y) 是解的合成函数。如果假定所分成的两个问题的输入规模大致相等,则DanC总 的计算时间可用下面的递归关系来估计: r(0=g)当输入规模n比较小时,直按求解运算G()的用时 4.1.1) 2T(n/2)+f(m)f(m)是 Combine用时 例4.1.1求n元数组中的最大和最小元素 最容易想到的算法是直接比较算法:将数组的第1个元素分别赋给两个临时 变量:f皿ax=A[l];fmin=A[l];然后从数组的第2个元素A[2]开始直到第n个 元素逐个与fmax和 fmin比较,在每次比较中,如果A[i]〉fmax,则用A[i 的值替换fax的值;如果A[i]<fmin,则用A[i]的值替换fmin的值;否则保 持fmax(fmin)的值不变。这样在程序结束时的fmax、fmin的值就分别是数组 的最大值和最小值。这个算法在最坏情况下,元素的比较次数是2(n-1),而平 均比较次数为3(n-1)/2。 如果采用分治的思想,我们可以给出算法,其时间复杂性在最坏和平均用时 均为3n/2-2
形，即将整个问题二分。以下用 A[1:n]来表示 n 个输入，用 DanC(p,q)表示处理 输入为 A[p:q]情况的问题。 分治法控制流程 DanC(p,q) global n，A[1:n]; integer m,p,q; // 1≤p≤q≤n if Small(p,q) then return G(p,q); else m=Divide(p,q); // p≤m<q return Combine(DanC(p,m),DanC(m+1,q)); endif end DanC 这里，Small(p,q)是一个布尔值函数，用以判断输入规模为 q-p+1 的问题 是否小到无需进一步细分即可容易求解。若是，则调用能直接计算此规模下子问 题解的函数 G(p,q). 而 Divide(p,q)是分割函数，决定分割点，Combine(x,y) 是解的合成函数。如果假定所分成的两个问题的输入规模大致相等，则 DanC 总 的计算时间可用下面的递归关系来估计： + = 是 用时 当输入规模 比较小时，直接求解运算 的用时 T n f n f n Combine g n G n T n 2 ( / 2) ( ) ( ) ( ) n ( ) ( ) （4.1.1） 例 4.1.1 求 n 元数组中的最大和最小元素 最容易想到的算法是直接比较算法：将数组的第 1 个元素分别赋给两个临时 变量：fmax=A[1]; fmin=A[1]; 然后从数组的第 2 个元素 A[2]开始直到第 n 个 元素逐个与 fmax 和 fmin 比较，在每次比较中，如果 A[i] > fmax，则用 A[i] 的值替换 fmax 的值；如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值；否则保 持 fmax（fmin）的值不变。这样在程序结束时的 fmax、fmin 的值就分别是数组 的最大值和最小值。这个算法在最坏情况下，元素的比较次数是 2(n-1)，而平 均比较次数为 3(n-1)/2。 如果采用分治的思想，我们可以给出算法，其时间复杂性在最坏和平均用时 均为 3n/2-2:
程序4-1-2递归求最大最小值算法伪代码 MaxMin(i,j,fmax,fmin)//A[l:n]是n个元素的数组,参数i,j /是整数,1≤i≤j≤n,使用该过程将数组A[i:j中的最大最小元 //分别赋给fmax和fmin。 global n, A[l: n]: integer i, j: fmax=fmin=A[i]:\\子数组A[i:j中只有一个元素 elseif i=j-1then\\子数组A[i:j中只有两个元素 if Ali]<ALj then fmin=A[i]: fmax=ALj else fmin=A[j]: fmax=ALi] endif else mid(i+j)/2」;\\子数组A[i:j中的元素多于两个 MaxMin(i, mid, gmax, gmin) MaxMin(mid+l, j, hmax, hmin); fmax=max(gmax, hmax) fmin=main(gmin, hmin) endif end Maxmin 如果用T(n)来表示 MaxMin所用的元素比较数,则上述递归算法导出一个 递归关系式: T(n)={1 2 4.1.2 2)+T(n/2b 当n是2的方幂时,设n=2,有 2(2T(n/4)+2) =47(n/4)+4+2 2=7(2) 2k-1+2k-2
程序 4-1-2 递归求最大最小值算法伪代码 MaxMin（i,j,fmax,fmin）//A[1:n]是 n 个元素的数组，参数 i，j //是整数，1≤i≤j≤n，使用该过程将数组 A[i:j]中的最大最小元 //分别赋给 fmax 和 fmin。 global n, A[1:n]; integer i, j; if i=j then fmax=fmin=A[i]; \\子数组 A[i:j]中只有一个元素 elseif i=j-1 then \\子数组 A[i:j]中只有两个元素 if A[i]<A[j] then fmin=A[i]; fmax=A[j]； else fmin=A[j]; fmax=A[i]; endif else mid=(i+j)/2; \\子数组 A[i:j]中的元素多于两个 MaxMin(i, mid, gmax, gmin); MaxMin(mid+1, j, hmax, hmin); fmax=max(gmax, hmax)； fmin=main(gmin, hmin)； endif end Maxmin 如果用 T(n)来表示 MaxMin 所用的元素比较数，则上述递归算法导出一个 递归关系式： + + > = = = ( / 2 ) ( / 2 ) 2 2 1 2 0 1 ( ) T n T n n n n T n (4.1.2) 当n是2 的方幂时，设 k n = 2 ，有 3 / 2 2 2 2 2 2 (2) 2 4 ( / 4) 4 2 2(2 ( / 4) 2) 2 ( ) 2 ( / 2) 2 1 1 1 1 = − = + − = + = + + = + + = + − ≤ ≤ − − ∑ n T T n T n T n T n k k i k k i L
无论是最好、最坏、还是平均情况, MaxMin所用的比较数都是3n/2-2,比前面 提到的算法(在最坏情况下)节省了25%的时间。实际上,任何一种以元素比较 为基础的找最大最小元素的算法,其元素比较数的下界是「3n/21-2。从这种意 义上来说, MaxMin算法是最优的。然而,由于需要Logn+1级的递归,每次递 归调用需要将i,j, fmax,fmin和返回地址的值保留到栈中,所以需要多占用 了内存空间。而且由于这些值出入栈时也会带来时间开销,特别当A中元素的比 较次数和整数i与j的比较次数相差无几时,递归求最大最小值算法未必比直接 求最大最小值算法效率高。 例4.1.2.搜索算法的时间下界 分析上节提到的折半搜索算法,我们已经知道其时间复杂度是O(logn) 事实上,我们可以用一个二元比较树来分析折半搜索算法的时间复杂性。以下是 n=9的二元比较树 n=9情况下折半搜索的二元比较树 由图可见,当ⅹ在数组A中时,算法在圆形顶点结束;不在A中时,算法 在方形顶点结束。因为23≤9<24,所以比较树的叶顶点都在4或5级上出现。 因而元素比较的最多次数为4。一般地有:当n∈p22)时,一次成功的折半搜 索至多做k次比较,而一次不成功的折半搜索或者做k-1次比较,或者做k次比 现在假设数组A[1:n满足:A[1]A[2]<…A[n。要搜索元素x是否在 A中。如果只允许进行元素间的比较而不允许对它们进行其它的运算,则所设计
无论是最好、最坏、还是平均情况，MaxMin 所用的比较数都是 3n/2-2，比前面 提到的算法(在最坏情况下)节省了 25％的时间。实际上，任何一种以元素比较 为基础的找最大最小元素的算法，其元素比较数的下界是 3n / 2 − 2 。从这种意 义上来说，MaxMin 算法是最优的。然而，由于需要log n +1级的递归，每次递 归调用需要将 i，j，fmax，fmin 和返回地址的值保留到栈中，所以需要多占用 了内存空间。而且由于这些值出入栈时也会带来时间开销，特别当 A 中元素的比 较次数和整数i与j 的比较次数相差无几时，递归求最大最小值算法未必比直接 求最大最小值算法效率高。 例 4.1.2．搜索算法的时间下界 分析上节提到的折半搜索算法，我们已经知道其时间复杂度是O(log n) 。 事实上，我们可以用一个二元比较树来分析折半搜索算法的时间复杂性。以下是 n=9 的二元比较树： n＝9 情况下折半搜索的二元比较树 由图可见，当 x 在数组 A 中时，算法在圆形顶点结束；不在 A 中时，算法 在方形顶点结束。因为 3 4 2 ≤ 9 < 2 ，所以比较树的叶顶点都在4或5 级上出现。 因而元素比较的最多次数为 4。一般地有：当 [ ) k k n 2 ,2 −1 ∈ 时，一次成功的折半搜 索至多做 k 次比较，而一次不成功的折半搜索或者做 k-1 次比较，或者做 k 次比 较。 现在假设数组 A[1:n]满足：A[1]< A[2]< …< A[n]。要搜索元素 x 是否在 A 中。如果只允许进行元素间的比较而不允许对它们进行其它的运算，则所设计 4 9 5 7 1 3 6 8 2
的算法称为以比较为基础的算法。任何以比较为基础的搜索算法的执行过程都可 以用一棵二元比较树来描述。每次可能的比较用一个内顶点表示,对应于不成功 的结果有一个外顶点(叶顶点)与之对应。线性搜索和折半搜索的二元比较树如 下 All 不成功 A[2 不成功 In 图4-1-1模拟线性搜索过程 不成功 不成功 x:AL(n+1)2 A(n+)2 A(n+1)y2 A|x:Ad(+12](x:A(m+/2H1 x: An 不成功不成功不成功 不成功不成功 不成功不成功不成功 图4-1-2模拟折半搜索过程 定理4.1.1设数组A[1:n]的元素满足A[1]<A[2]<…<A[n]。则以比较为 基础,判断x∈A[1:n]的任何算法,在最坏情况下所需的最少比较次数 Find(n) 不小于1og(n+1) 证明通过考察模拟求解搜索问题的各种可能算法的比较树可知,Find(n) 不大于树中由根到一个叶子的最长路径的距离。也就是说,在最坏情况下每种搜 索算法的比较次数都是比较树中由根到叶顶点的最长距离。在所有的树中,这个
的算法称为以比较为基础的算法。任何以比较为基础的搜索算法的执行过程都可 以用一棵二元比较树来描述。每次可能的比较用一个内顶点表示，对应于不成功 的结果有一个外顶点（叶顶点）与之对应。线性搜索和折半搜索的二元比较树如 下： 图 4-1-1 模拟线性搜索过程 . . . . . . 图 4-1-2 模拟折半搜索过程 定理 4.1.1 设数组 A[1:n]的元素满足 A[1]< A[2]< …< A[n]。则以比较为 基础，判断 x ∈ A[1: n]的任何算法，在最坏情况下所需的最少比较次数 Find(n) 不小于log(n+1). 证明 通过考察模拟求解搜索问题的各种可能算法的比较树可知，Find(n) 不大于树中由根到一个叶子的最长路径的距离。也就是说，在最坏情况下每种搜 索算法的比较次数都是比较树中由根到叶顶点的最长距离。在所有的树中，这个 x:A[1] x:A[2] x:A[n] 不成功 不成功 不成功 不成功 x:A[(n+1)/2] x:A[(n+1)/2] x:A[1] x:A[(n+1)/2-1] x:A[(n+1)/2] x:A[(n+1)/2+1] x:A[n] 不成功 不成功 不成功 不成功 不成功 不成功 不成功 不成功