主要内容 般方法 2.二分检索 3.找最大和最小元素 4.归并分类 5.快速分类 6.选择问题 7.斯特拉森矩阵乘法
主要内容 1. 一般方法 2. 二分检索 3. 找最大和最小元素 4. 归并分类 5. 快速分类 6. 选择问题 7. 斯特拉森矩阵乘法
31一般方法 令对大规模问题的求解 利用分治法求解大规模问题 1.基本思想 分而治之方法与软件设计的模块化方法非常相似。 为解决一个大问题,可以(1)把它分解成两个或多个 更小的问题;(2)分别解决每个小问题;(3)把各 小问题的解答组合起来,即可得到原问题的解。 小问题通常与原问题相似或同质,因而可以递归地 使用分而治之策略解决
❖ 对大规模问题的求解 ❖ 利用分治法求解大规模问题 1.基本思想 分而治之方法与软件设计的模块化方法非常相似。 为解决一个大问题,可以(1)把它分解成两个或多个 更小的问题;(2)分别解决每个小问题;(3)把各 小问题的解答组合起来,即可得到原问题的解。 小问题通常与原问题相似或同质 ,因而可以递归地 使用分而治之策略解决。 3.1 一般方法
逐步细化的过程 /子问题 /子问题求解 al 问题 子结果 q2 12 A 分解 合并 k k 通常,子问题与原始问题“同质
Q q2 qk q1 子问题 ... a2 ak a1 子问题求解 ... 问题 A 子结果 分解 合并 逐步细化的过程 通常,子问题与原始问题“同质
例1找伪币]假设16枚金币中有一枚是伪造的,真假金 币的区别仅是重量不同,利用一个没有砝码的天平作工具, 找出这枚伪造的金币 例2[金块问题]有一个老板有一袋金块。每个月将有两 名雇员会因其优异的表现分别被奖励一个金块。按规矩, 排第一的雇员将得到袋中最重的金块,排名第二的雇员 将得到袋中最轻的金块。根据这种方式,除非有新金块 快加入袋中,否则第一名雇员所得到的金块总是比第二 名雇员所得到的金块重,如果有新的金块周期性的加入 袋中,则每个月都必须找出最重和最轻的金块。假设有 台比较重量的仪器,希望用最少的比较次数找出最重 和最轻的金块。 问题的分解策略有多种
例1 [找伪币] 假设16 枚金币中有一枚是伪造的,真假金 币的区别仅是重量不同,利用一个没有砝码的天平作工具, 找出这枚伪造的金币。 例2 [金块问题]有一个老板有一袋金块。每个月将有两 名雇员会因其优异的表现分别被奖励一个金块。按规矩, 排第一的雇员将得到袋中最重的金块,排名第二的雇员 将得到袋中最轻的金块。根据这种方式,除非有新金块 快加入袋中,否则第一名雇员所得到的金块总是比第二 名雇员所得到的金块重,如果有新的金块周期性的加入 袋中,则每个月都必须找出最重和最轻的金块。假设有 一台比较重量的仪器,希望用最少的比较次数找出最重 和最轻的金块。 问题的分解策略有多种
例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)∥≤mDVDE(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 nn0 其中,f(n)是合并各部分解的时间,k,m均为常数