文档介绍：第二章分治法 ——“分”而治之
一般方法
对大规模问题的求解
利用分治法求解大规模问题
分而治之方法法与软件设计的模块化方法非常相似。为解决一个大问题,可以(1)把它分解成两个或多个更小的问题;(2)分别解决每个小问题;(3)把各小问题的解答组合起来,即可得到原问题的解。
小问题通常与原问题相似或同质,因而可以递归地使用分而治之策略解决。
12/1/2017
本章教学要求及重点难点
理解分治法的基本思想
掌握二分检索中成功检索和不成功检索各自时间复杂度的计算方法
掌握归并分类的基本方法
掌握快速分类的算法及对此算法的时间复杂度分析
掌握最坏情况下选择问题的时间复杂度分析
重点:二分检索、找最大和最小元素、归并分类、快速分类。
难点:选择问题的算法及对该算法的时间复杂度分析
12/1/2017
通常,子问题与原始问题“同质”
12/1/2017
例[找伪币] 假设16 枚金币中有一枚是伪造的,真假金币的区别仅是重量不同(伪币轻一些),利用一个没有砝码的天平作工具,找出这枚伪造的金币。
方法1:比较硬币1和2的重量,有一个轻则找到; 否则比较硬币3和4,依次比较下去,直到找到。最多8次比较。
方法2:利用分治法。16个硬币分为两组,每组8个,比较重量,伪币在轻的一组。将轻的一组再分为两组,每组4个……继续划分下去,依次每组2个,每组1个,此时找到。
12/1/2017
分治策略的抽象化控制
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//
BINE(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():对输入规模为q-p+1的子问题进一步分解,返回值为[p,q]区间进一步的分割点(SMALL(p,q)不为真时);
COMBINE(x,y):子结果的合并函数,将区间[p,m]和[m+1,q]上的子问题的解合并成上级区间[p,q]上的“较完整”的解。当p=1,q=n时,就得到整个问题的解。
2. 分治策略的抽象化控制
12/1/2017
DANDC的计算时间
若所分成的两个子问题的输入规模大致相等,则DANDC总的计算时间可用递归关系式表示,如下:
g(n) n足够小
T(n) =
2T(n/2) + f(n) 否则
注:
T(n):表示输入规模为n的DANDC计算时间
g(n):表示对足够小的输入规模直接求解的计算时间
f(n):BINE对两个子区间的子结果进行合并
的时间
(该公式针对具体问题有各种不同的变形)
12/1/2017
二分检索(折半查找)
1. 问题的描述
已知一个按非降次序排列的元素表a1, a2, …,an,判定某给定的元素x是否在该表中出现。
若是,则找出x在表中的位置并返回其所在下标
若非,则返回0值。
12/1/2017
分治求解策略分析:
定义问题的形式描述: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, ak+2, …,an,x)
对于I2,若ak=x,则有解k,对I1、I3不用再求解;否则,
若x<ak,则只在I1中求解,对I3不用求解;
若x>ak,则只在I3中求解,对I1不用求解;
I1 、I3上的求解可再次采用分治方法划分后求解(递归过程)
12/1/2017
2. 二分检索算法
二分检索
procedure BINSRCH(A,n,x,j)
integer low,high,mid,j,n;
low←1; high←n;
while low≤high do
mid ←
case
:x<A(mid):high←mid-1
:x>A(mid):low ←mid+1
:else:j←mid;return
endcase
repeat
j←0
end BINSRCH
注:
给定一个按非降次序排列的元素数组A(1:n),n≥1,判断x是否出现。
若是,置j,使得x