第二章分治法( Divide and Conquer) “分”而治之 2.1一般方法 对大规模问题的求解 利用分治法求解大规模问题 子问题 问题求解 1.分治策略基本思想 当问题的规模较大。叫 结果 而无法直接求解时,将分 合并 整个问题分成若干个小 问题,然后分而治之。 可用递归过程描述, 一般情况下,子问题与原始问题“同质
第二章 分治法（Divide and Conquer) —— “分”而治之 2.1 一般方法 ◼ 对大规模问题的求解 ◼ 利用分治法求解大规模问题 Q q2 qk q1 子问题 ... a2 ak a1 子问题求解 ... 问题 A 子结果 分解 合并 逐步细化的过程 1.分治策略基本思想 当问题的规模较大 而无法直接求解时，将 整个问题分成若干个小 问题，然后分而治之。 可用递归过程描述。 一般情况下，子问题与原始问题“同质
2.分治策略的抽象化控制过 算法21分治策略的抽象化控制注 procedure DANDC(p, g) k=2:二分是最常用的分解策略; global nA(1: n > SMALL(p,q):布尔函数,判断输 integer m,p,q;∥1p≤q≤n 入规模q-p+1是否足够小而无需再 进一步分航就可求解; if SMALL(p, g) >G(p,q):当 SMALL(pq)为真时, then return(G(p, g)) 对输入规模为q-p+1的子问题求解 else DVDE(pq):当规模q-p+1还较 m← DIVIDE(p,q)/lp≤m<q∥ 大时,对规模为q-p+1的子问题进 retun (COMBINE(DANDC(p, m), 步分解,返回值为[pq]区间进 DANDC(m+1, g)) 步的分割点; endif COMBIN(xy):子结果的合并函 end dand 数,将区间pm和[m+1q]上的子 问题的解合并成区间[q]上的 “较完整”的解。当p=1,q=n时, 就得到整个问题的解
算法2.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)： 当SMALL(p,q)为真时， 对输入规模为q-p+1的子问题求解； ➢ DIVIDE(p.q)：当规模q-p+1还较 大时，对规模为q-p+1的子问题进 一步分解，返回值为[p,q]区间进 一步的分割点； ➢ COMBINE(x,y)：子结果的合并函 数，将区间[p,m]和[m+1,q]上的子 问题的解合并成区间[p,q]上的 “较完整”的解。当p=1,q=n时， 就得到整个问题的解。 2. 分治策略的抽象化控制过程
■ DANDC的计算时间 若所分成的两个子问题的规模大致相等,则 DANDO总的 计算时间可用递归关系式表示如下: gn) n足够小 T(n 2T(n/2)+f(n)否则 注: T(n):表示输入规模为η的 DANDO计算时间 g(η):表示对足够小的输入规模直接求解的计算时间 f(n):表示 COMBINE对两个子区间的子结果进行合并 的时间 (该公式针对具体问题有各种不同的变形)
◼ DANDC的计算时间 若所分成的两个子问题的规模大致相等，则DANDC总的 计算时间可用递归关系式表示如下： g(n) n足够小 T(n) = 2T(n/2) + f(n) 否则 注： ➢ T(n)：表示输入规模为n的DANDC计算时间 ➢ g(n)：表示对足够小的输入规模直接求解的计算时间 ➢ f(n)：表示COMBINE对两个子区间的子结果进行合并 的时间 （该公式针对具体问题有各种不同的变形）
2.2二分检索(折半查找) 1.问题的描述 已知一个按非降次序排列的元素表a1, a2,,an,判定某给定的元素x是否在该表中 出现。 若是,则找出X在表中的位置并返回其所在位置 的下标 >若非,则返回0值
2.2 二分检索（折半查找） 1. 问题的描述 已知一个按非降次序排列的元素表a1 , a2 , …,an，判定某给定的元素x是否在该表中 出现。 ➢ 若是，则找出x在表中的位置并返回其所在位置 的下标 ➢ 若非，则返回0值
问题的形式描述: l=(n,a1,a2,…,an,× 可题分解:选取下标k,由此将|分解为3个子问题: =(k-1,a1,a2,…ak1 l2=(1,ak, 3=(n-k,ak+1,a2,…anX) 对于l2,若a=X,则有解k,对l1、3不用再求解;否则, 若<ak,则只在l1中求解,对3不用求解; 若X>ak,则只在l3中求解,对l1不用求解; 对1、l3的求解可再次采用分治方法求解
问题的形式描述： I=(n, a1 , a2 , …,an ,x) ◼ 问题分解：选取下标k，由此将I分解为3个子问题： I1=(k-1, a1 , a2 , …,ak-1 ,x) I2=(1, ak ,x) I3=(n-k, ak+1, a2 , …,an ,x) ➢ 对于I2，若ak=x，则有解k，对I1、I3不用再求解；否则， ➢ 若x<ak，则只在I1中求解，对I3不用求解； ➢ 若x>ak，则只在I3中求解，对I1不用求解； ➢ 对I1 、I3的求解可再次采用分治方法求解