例3[矩阵乘法]两个n×n阶的矩阵A与B的乘积是另 个n×n阶矩阵Cc的元素可表示为 C(,j)=∑A(k)*B(k,),1≤i≤n,1≤j≤n 其时间复杂度为o(n3)。可以采用矩阵分块 乘法降低时间复杂度。 先将A、B分别分割为4个n/2×n2的矩阵, 然后组合 分治法自然导致了递归算法的使用。在许多例子 里,这些递归算法在递归程序中得到了很好的运用
例3 [矩阵乘法]两个n×n阶的矩阵A与B的乘积是另 一个n×n阶矩阵C,C的元素可表示为： C i j A i k B k j i n j n n k = = ( , ) ( , ) * ( , ) ,1 ,1 1 其时间复杂度为O(n3 )。可以采用矩阵分块 乘法降低时间复杂度。 先将A、B分别分割为4个n/2×n/2的矩阵， 然后组合。 分治法自然导致了递归算法的使用。在许多例子 里，这些递归算法在递归程序中得到了很好的运用
2.分治策略的抽象化控制 算法31分治策略的抽象化控制注: procedure DANDC(p, q k=2:二分是最常用的分解策略; global, A(1: n) > SMALL(P,q):布尔函数,判断输入 integer m,p,q;∥1≤p≤q≤n∥ 规模q-p+1是否足够小而无需再进 if SMall(p, q) 步分就可求解; then return(G(p, >G(p,q):对输入规模为qp+1的子问 else 题求解( SMALL(pq为真时); m←DVDE(p,q)∥≤m<q >DVDE(pq):对输入规模为q-p+ 的子问题进一步分解,返回值为[pq] return( COMBINE(DANDC(Pm,区间进一步的分割点( SMALL(p,q DANDO(m+1,q)为假时 endif COMBINE(xy):子结果的合并函数, end dand 将区间[p,m和[m+1,q上的子问题 的解合并成上级区间[p,q]上的“较 完整”的解。当p=1,qn时,就得到 整个问题的解
算法3.1 分治策略的抽象化控制 procedure DANDC(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(DANDC(p,m), DANDC(m+1,q))) endif end DANDC 注： ➢ k=2: 二分是最常用的分解策略； ➢ SMALL(p,q)：布尔函数，判断输入 规模q-p+1是否足够小而无需再进一 步分就可求解； ➢ G(p,q)：对输入规模为q-p+1的子问 题求解（SMALL(p,q)为真时）； ➢ DIVIDE(p.q)：对输入规模为q-p+1 的子问题进一步分解，返回值为[p,q] 区间进一步的分割点（SMALL(p,q) 为假时； ➢ COMBINE(x,y)：子结果的合并函数， 将区间[p,m]和[m+1,q]上的子问题 的解合并成上级区间[p,q]上的“较 完整”的解。当p=1,q=n时，就得到 整个问题的解。 2. 分治策略的抽象化控制
DANDC的计算时间 若所分成的两个子问题的输入规模大致相等,则 DANDC 总的计算时间可用递归关系式表示,如下: g(n) n足够小 2T(m/2)+fn)否则 注: T(n)}:表示输入规模为η的 DANDO计算时间 g(η):表示对足够小的输入规模直接求解的计算时间 f(m):表示 COMBINE对两个子区间的子结果进行合并 的时间 (该公式针对具体问题有各种不同的变形)
❖ DANDC的计算时间 若所分成的两个子问题的输入规模大致相等，则DANDC 总的计算时间可用递归关系式表示，如下： g(n) n足够小 T(n) = 2T(n/2) + f(n) 否则 注： ➢ T(n)：表示输入规模为n的DANDC计算时间 ➢ g(n)：表示对足够小的输入规模直接求解的计算时间 ➢ f(n)：表示COMBINE对两个子区间的子结果进行合并 的时间 （该公式针对具体问题有各种不同的变形）
分治法的另一种模型表示 &o proc dividandconquer(n) 冷ifn≤= no then g(n) elsei divid n into small suninstances n1 n2n3.nk for j=1 to k do yisdividandconquer(ni) return merge(y1.yk)] end dividandconguer Tn)=G(n)n≤≡n0 kT(n/m)+f(n)n>nO 其中,f(n)是合并各部分解的时间,km均为常数
分治法的另一种模型表示 ❖ proc dividandconquer(n) ❖ if n<=n0 then g(n) ❖ else { divid n into small suninstances ❖ n1 n2 n3…nk ❖ for i=1 to k do ❖ yi=dividandconquer(ni) ❖ return merge(y1…yk) } ❖ end dividandconquer T(n)= G(n) n<=n0 kT(n/m)+f(n) n>n0 其中，f(n)是合并各部分解的时间，k,m均为常数
进一步思考 n0选择多大合适? ◆原问题应该分解成几个子问题? 大量实践得出子问题的规模大致相当分治的 效率较好 般进行2分法
进一步思考 ❖ n0选择多大合适？ ❖ 原问题应该分解成几个子问题？ ❖ 大量实践得出子问题的规模大致相当分治的 效率较好。 ❖ 一般进行2分法