第二章分治法( 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,则只在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不用再求解；否则， ➢ 若xak，则只在I3中求解，对I1不用求解； ➢ 对I1 、I3的求解可再次采用分治方法求解
2.二分检索 分检索:每次选取中间元素的下标 算法2.3二分检索 procedure BINSRCH(A, n, x,j integer low, high, mid,j, n 注 oW←1;high←n 给定一个按非降次序排列 While low≤ high do 的元素数组A(1n),n≥1, mid←(ow+hgh2」 判断x是否出现。 case X≤A(md)high←mid-1 若是,置j,使得ⅹ=A(j) X>A(mid)lW←mid+1 若非,j=0 else j←mid; return endcase repeat -0 end binsrch
2. 二分检索 二分检索：每次选取中间元素的下标 算法2.3 二分检索 procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low←1; high←n; while low≤high do mid ← case :xA(mid):low ←mid+1 :else:j←mid;return endcase repeat j←0 end BINSRCH(low + high)/2 注： 给定一个按非降次序排列 的元素数组A(1:n)，n≥1, 判断x是否出现。 •若是，置j，使得x=A(j) •若非，j=0
例21:设A(1:9)=(-15,-6,0,7,9,23,54,82,101) 在A中检索x=101,-14,82。执行轨迹见下表1 表1运行轨迹示例 x=101 x=-14 low high mid low high d OW high 9 5 5 9 5 找不到 找到 找到 成功的检索 不成功的检索 成功的检索
例2.1：设A(1:9)=(-15，-6，0，7，9，23，54，82，101) 在A中检索x=101，-14，82。执行轨迹见下表1 表1 运行轨迹示例 x=101 x=-14 x=82 low high mid low high mid low high mid 1 9 5 1 9 5 1 9 5 6 9 7 1 4 2 6 9 7 8 9 8 1 1 1 8 9 8 9 9 9 2 1 找不到 找到 找到 成功的检索 不成功的检索 成功的检索
定理21过程B| NSRCH(A,n,xj)能正确运行 证明 1)在具体指定A中的数据元素及x的数据类型后,算法中的所有运算都 能按要求正确运行——即首先满足确定性和能行性 2)终止性 算法初始部分置low←1,high←n ①若η=0,不进入循环,j置0,算法终止 ②否则,进入循环,计算mid, 或X=A(mid),j置为mid,算法终止: 或≤A(mid),置high←mid-1,搜索范围实际缩小为[ow,md-1 进入下次循环,对[md+1,hgh区间不做进一步搜索; 〉或x>A(mid),置low←mid+1,进入下次循环;搜索范围实际缩小 为[mid+1,high],对[ow,md-区间不做进一步搜索; 因low,high,mid都是整型变量,故按照上述规则,在有限步内,或 找到某个md,有Amid)=x;或变得 lehigh,在A中没有找到任何元 素等于ⅹ,算法终」
定理2.1 过程BINSRCH(A,n,x,j)能正确运行 证明： 1）在具体指定A中的数据元素及x的数据类型后，算法中的所有运算都 能按要求正确运行——即首先满足确定性和能行性 2）终止性 算法初始部分置low←1, high←n ① 若n=0，不进入循环，j置0，算法终止 ② 否则，进入循环，计算mid, ➢ 或 x=A(mid)，j置为mid，算法终止； ➢ 或xA(mid)，置low←mid+1，进入下次循环；搜索范围实际缩小 为[mid+1, high]，对[low, mid-1]区间不做进一步搜索； 因low, high, mid都是整型变量，故按照上述规则，在有限步内，或 找到某个mid，有A(mid) = x；或变得low>high，在A中没有找到任何元 素等于x，算法终止
3.性能分析 1)空间特性 n+5个空间位置(A,xj,mid, low, higl O 2)时间特性 区分以下情况进行分析 成功检索:指所检索的x恰好在A中出现 由于A中共有n个元素,故成功检索恰好有n种可能的情况 不成功检索:指x不出现在A中。 根据取值,不成功检索共有n艹1种可能的情况(取值区间): xA(n) 成功/不成功检索的最好情况:执行步数最少,计算时间最短 成功/不成功检索的最坏情况:执行步数最多,计算时间最长 >成功/不成功检索的平均情况:一般情况下计算时间的平均值
3. 性能分析 1）空间特性 n+5个空间位置(A,x,j, mid,low,high)——О(n) 2) 时间特性 区分以下情况进行分析 ➢ 成功检索：指所检索的x恰好在A中出现。 由于A中共有n个元素，故成功检索恰好有n种可能的情况 ➢ 不成功检索：指x不出现在A中。 根据取值，不成功检索共有n+1种可能的情况（取值区间）： xA(n) ➢成功/不成功检索的最好情况：执行步数最少，计算时间最短 ➢成功/不成功检索的最坏情况：执行步数最多，计算时间最长 ➢成功/不成功检索的平均情况：一般情况下计算时间的平均值
实例分析(例2.1) 运算的频率计数 procedure BINSRCH(A, n, x,j) 1. While循环体外语句的频 integer low, high, mid,j, n 率计数为1 oWA(md):loW←mid+1 else:i←mid; return endcase 3.case语句的分析:假定只 repeat 需一次比较就可确定case ←0 语句控制是三种情况的哪 end bINSRCH 种
实例分析（例2.1） 运算的频率计数 1. while循环体外语句的频 率计数为1 2. 集中考虑while循环中x与A 中元素的比较运算 ——其它运算的频率计数 与比较运算相同的数量级 3. case语句的分析：假定只 需一次比较就可确定case 语句控制是三种情况的哪 一种。 procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low←1; high←n; while low≤high do mid ← case :xA(mid):low ←mid+1 :else:j←mid;return endcase repeat j←0 end BINSRCH (low + high)/2