形,即将整个问题二分。以下用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: