2009-7-27
第二章 分治法
——―分”而治之
2.1 一般方法
对大规模问题的求解
利用分治法求解大规模问题
1.基本思想分而治之方法法与软件设计的模块化方法非常相似。
为解决一个大问题，可以 （ 1）把它 分解 成两个或多个更小的问题；（ 2） 分别解决 每个小问题；（ 3）把各小问题的解答 组合 起来，即可得到原问题的解。
小问题通常与原问题相似或同质,因而可以 递归 地使用分而治之策略解决。
2009-7-27
Q q 2
q k
q 1
子 问 题
.,,
a 2
a k
a 1
子 问 题 求 解
.,,
问 题
A
子 结 果合 并分 解逐 步 细 化 的 过 程通常，子问题与原始问题,同质”
2009-7-27
例 [找伪币 ] 假设 16 枚金币中有一枚是伪造的，真假金币的区别仅是重量不同 (伪币轻一些），利用一个没有砝码的天平作工具，找出这枚伪造的金币。
方法 1：比较硬币 1和 2的重量，有一个轻则找到；
否则比较硬币 3和 4，依次比较下去，直到找到。最多 8次比较。
方法 2：利用分治法。 16个硬币分为两组，每组 8个，
比较重量，伪币在轻的一组。将轻的一组再分为两组，每组 4个 …… 继续划分下去，依次每组 2个，每组 1个，此时找到。
2009-7-27
算法 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),对输入规模为 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,分治策略的抽象化控制
2009-7-27
DANDC的计算时间若所分成的两个子问题的输入规模大致相等，则 DANDC
总的计算时间可用递归关系式表示，如下：
g(n) n足够小
T(n) =
2T(n/2) + f(n) 否则注：
T(n),表示输入规模为 n的 DANDC计算时间
g(n),表示对足够小的输入规模直接求解的计算时间
f(n),表示 COMBINE对两个子区间的子结果进行合并的时间
（该公式针对具体问题有各种不同的变形）
2009-7-27
2.2 二分检索（折半查找）
1,问题的描述已知一个按 非降次序 排列的元素表 a1,
a2,…,a n,判定某给定的元素 x是否在该表中出现。
若是，则找出 x在表中的位置并返回其所在下标
若非，则返回 0值。
2009-7-27
分治求解策略分析,
定义问题的 形式描述,I=(n,a1,a2,…,a n,x)
问题分解：选取下标 k，由此将 I分解为 3个子问题：
I1=(k-1,a1,a2,…,a k-1,x)
I2=(1,ak,x)
I3=(n-k,ak+1,a2,…,a n,x)
对于 I2，若 ak=x，则有解 k，对 I1,I3不用再求解；否则，
若 x<ak，则只在 I1中求解，对 I3不用求解；
若 x>ak，则只在 I3中求解，对 I1不用求解；
I1,I3上的求解可再次采用分治方法划分后求解（ 递归过程 ）
2009-7-27
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
:x<A(mid):high←mid -1
:x>A(mid):low ←mid+1
:else:j←mid;return
endcase
repeat
end BINSRCH
h ig h ) / 2( lo w?
注,
给定一个按非降次序排列的元素数组 A(1:n)，
n≥1,判断 x是否出现。
若是，置 j，使得 x=A(j)
若非,j=0
2009-7-27
例 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 找不到 找到找到成功 的检索 不成功 的检索 成功 的检索
2009-7-27
3,算法的正确性证明定理 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，算法终止；
或 x<A(mid)，置 high←mid -1，搜索范围实际缩小为 [low,mid-1]，
进入下次循环，对 [mid+1,high]区间不做进一步搜索；
或 x>A(mid)，置 low←mid+1,进入下次循环；搜索范围实际缩小为 [mid+1,high]，对 [low,mid-1]区间不做进一步搜索；
因 low,high,mid都是整型变量，故按照上述规则，在 有限步内,或找到某个 mid，有 A(mid) = x；或变得 low>high，在 A中没有找到任何元素等于 x，算法终止。
2009-7-27
4,性能分析
1）空间特性
n+5个空间位置 ——О(n)
2) 时间特性区分以下情况，并进行相应的分析
成功检索,所检索的 x出现在 A中。
成功检索情况共有 n种,x恰好是 A中的某个元素,A中共有 n个元素，故有 n
种可能的情况
不成功检索,所检索的 x不出现在 A中。
不成功检索情况共有 n+1种,x<A(1),或 A(i)<x<A(i+1),1≤i<n -1或 x>A(n)
成功 /不成功检索的最好情况,执行步数最少，计算时间最短
成功 /不成功检索的最坏情况,执行步数最多，计算时间最长
成功 /不成功检索的平均情况,一般情况下的计算时间
2009-7-27
实例分析（例 2.1）
频率计数特征
1,while循环体外语句的频率计数为 1
2,集中考虑 while循环中的 x与 A中元素的比较（其它运算的频率计数与之有相同的数量级）
假定只需一次比较就可确定 case语句控制是三种情况的哪一种。查找每个元素所需的元素比较次数统计如下：
A ⑴ ⑵ ⑶ ⑷ ⑸ ⑹ ⑺ ⑻ ⑼
元素 -15 -6 0 7 9 23 54 82 101
成功检索 比较次数 3 2 3 4 1 3 2 3 4
不成功检索 比较次数 3 3 3 4 4 3 3 3 4 4
2009-7-27
成功检索最好,1次最坏,4次平均,（ 3+2+3+4+1+3+2+3+4） /9≈ 2.77次
不成功检索最好,3次最坏,4次平均,(3+3+3+4+4+3+3+3+4+4)/10 = 3.4次
2009-7-27
二元比较树
算法执行过程的 主体 是 x与一系列中间元素 A(mid)比较。可用一棵二元树描述这一过程，
并称之为 二元比较树 。
构造,比较树由称为 内结点 和外结点 的两种结点组成：
内结点,表示一次元素比较，
用圆形结点表示，存放一个
mid值；代表一次成功检索；
外结点,在二分检索算法中表示一种不成功检索的情况，用方形结点表示。
路 径,表示一个元素的比较序列。
例 2.1的二元比较树
5
2 7
1 3 6
8
4
9
2009-7-27
基于二元比较树的分析
若 x在 A中出现，则算法的执行过程在一个圆形的 内结点 处结束。
若 x不在 A中出现，则算法的执行过程在一个方形的 外结点 处结束
——外结点不代表元素的比较，因为比较过程在该外结点的上一级的内结点处结束。
5
2 7
1 3 6
8
4
9
例 2.1的二元比较树
2009-7-27
定理 2.2 若 n在区域 [2k-1,2k)中，则对于 一次成功的检索,BINSRCH至多做 k次比较；对于 一次不成功的检索,或者做 k-1次比较，或者做 k
次比较。
证明：
要点：
成功检索都在内结点处结束，不成功检索都在外结点处结束
当 2k-1≤n< 2k时，所有内结点在 1至 k级，所有外结点在第 k级或第 k+1级，
故：成功检索在 i级终止所需要的元素比较次数是 i
不成功检索在 i级外部结点终止的元素比较次数是 i-1
2009-7-27
BINSRCH计算复杂度的理论分析
1）不成功检索的最好、最坏和平均情况的计算时间均为 ——外结点处在最末的两级上；
2）最好情况下的成功检索的计算时间为最坏情况下的成功检索的计算时间为
Θ (log n)
Θ(1)
Θ (log n)
2009-7-27
3）平均情况下的成功检索的计算时间分析利用 外部结点和内部结点到根距离和之间的关系 进行推导：
记，
由根到所有内结点的距离之和称为 内部路径长度,记为 I；
由根到所有外部结点的距离之和称为 外部路径长度,记为 E。
则有,E=I+2n
记，
U(n)是平均情况下不成功检索的计算时间，则 U(n) = E/(n+1)
S(n)是平均情况下成功检索的计算时间，则 S(n) = I/n+1
利用上述公式，可有,S(n) = (1+1/n)U(n) -1
当 n→∞,S(n) ∝ U(n),而 U(n) =
所以 S(n) =
Θ (log n)
Θ (log n)
2009-7-27
4,以比较为基础检索的时间下界问题,设 n个元素的数组 A(1:n)有 A(1)< A(2) < …<
A(n)。检索一给定元素 x是否在 A中出现。
定理 2.2给出了二分检索算法的时间下界，是否预计还存在有以元素比较为基础的另外的检索算法，
它在最坏情况下比二分检索算法在计算时间上有 更低的数量级?
以比较为基础的算法,假定算法中只允许进行元素间的 比较,而不允许对它们实施其它运算。
2009-7-27
注：每个 内结点 表示一次元素的比较。每棵比较树中恰好含有 n个内结点，
分别与 n个不同 i值相对应；每个 外结点 对应一次不成功的检索，并恰好又 n+1个外结点对应于 n+1中不成功检索的情况。
任何以比较为基础的检索算法，其执行过程都可以用二元比较树来描述。
2009-7-27
以比较为基础的有序检索问题最坏情况的时间下界
定理 2.3 设 A(1:n)含有 n(n≥1) 个不同的元素，排序为 A(1)<
A(2) < …< A(n) 。又设用以比较为基础的算法去判断是否,则这样的任何算法在最坏情况下所需的最小比较次数 FIND(n)有：
n):A (1x?
1)l o g ( nF I N D ( n )
证明：从模拟求解检索问题算法的比较树可知,FIND(n)不大于树中由根到一个叶子的最长路径的距离。而所有树中必定有 n个内结点与 x在 A中的 n中可能的出现相对应。如果一棵二元树的所有内结点所在的级数小于或等于 k，则最多有 2k-1个内结点。故 n≤2 k-1,即
1)l o g ( nkF I N D ( n )
2009-7-27
任何一种以比较为基础的算法，在 最坏情况 下的计算时间都 不低于 Ο(logn)。因此，
不可能存在最坏情况比二分检索数量级还低的算法。
二分检索是解决检索问题的 最优 的 最坏情况 算法。
2009-7-27
2.3 找最大和最小元素问题描述：给定含有 n个元素的集合，
在其中找出最大和最小元素。
2009-7-27
1,直接找最大和最小元素算法 2.5 直接找最大和最小元素
procedure STRAITMAXMIN(A,n,max,min)
//将 A中的最大值置于 max，最小值置于 min//
Integer i,n
max←min←A(1)
for i←2 to n do
if A(i) > max then
max←A(i)
endif
if A(i) < min then
min←A(i)
endif
repeat
end STRAITMAXMIN
算法的性能：
只考虑算法中的 比较运算,以此代表算法的执行特征；
该算法最好、最坏、
平均情况下均需要做
2（ n-1)次元素比较
2009-7-27
STRAITMAXMIN算法的一种简单改进形式,
procedure STRAITMAXMIN1(A,n,max,min)
integer i,n
max←min←A(1)
for i←2 to n do
if A(i) > max then max←A(i) endif
else if A(i) < min then min←A(i) endif
repeat
end STRAITMAXMIN1
这使得，
最好情况,按 递增次序 排列，元素比较次数为 n-1次
最坏情况,按 递减次序 排列，元素比较次数为 2(n-1)次
平均情况,元素比较次数为 3(n-1)/2次
2009-7-27
2,分治求解策略记问题的一个实例为：
I = (n,A(1),…,A(n))
采用二分法将 I分成两个子集合处理
I1 = (,A(1),…,A( ))，和
I2 = (n-,A( +1),…,A(n))
则有，
MAX(I) = max(MAX(I1),MAX(I2))
MIN(I) = min(MIN(I1),MIN(I2))
采用递归的设计策略，得到以下算法：
n/2n/2
n/2n/2
2009-7-27
3,一种递归求解策略算法 2.6 递归求取最大和最小元素
procedure MAXMIN(i,j,fmax,fmin)
//A(1:n)是含有 n个元素的数组，参数 I,j是整数,1≤i,j≤n //
//该过程把 A(i:j)中的最大和最小元素分别赋给 fmax和 fmin //
integer i,j;global n,A(1:n)
case
:i=j,fmax←fmin←A(i) // 只有一个元素
:i=j-1:if A(i)<A(j) then fmax←A(j);fmin←A(i)
else fmax←A(i);fmin←A(j) // 两个元素的情况
endif
:else,mid← // 取中
call MAXMIN(i,mid,gmax,gmin)
call MAXMIN(mid +1,j,hmax,hmin)
fmax←max(gmax,hmax); fmin←min(gmin,hmin)
end case
end MAXMIN
j)/2(i?
2009-7-27
例：在 A(1:9) = (22,13,-5,-8,15,60,17,31,47)上执行算法 2.6
每个结点内的值分别是：
i,j,fmax,fmin
递归调用递归调用分解过程递归调用的返回
2009-7-27
性能分析 (T(n)表示元素比较数）
0 n=1
T(n) = 1 n=2
n>2
当 n是 2的幂时 (n=2k),化简上式有，
T(n)=2T(n/2) +2
=2(2T(n/22) + 2) + 2 = 22T(n/22 ) + 22 + 2
= 22(2T(n/23 )+2)+22+2 = 23T(n/23 )+23+22+2
=……= 2 k-1T(n/2k-1 ) +(2k-1+…+2 2+21)
= 2k-1T(2) +(2k-1+…+2 2+21)
= n/2 + (2k – 1 – 1) = n/2 + n – 2 = 3n/2 – 2
2)n / 2T()n / 2T(
2009-7-27
性能分析
1）与 STRAITMAXMIN算法相比，比较次数减少了 25%
（ 3n/2-2,2n-2)。
已经达到了以 元素比较为基础 的找最大最小元素的算法计算时间的 下界,
2）存在的问题：
空间占用量大
有 级的递归，入栈参数：
i,j,fmax,fmin和返回地址五个值。
时间可能不比预计的理想如果元素 A(i)和 A(j)的比较与 i和 j的比较 相差不大 时，算法 MAXMIN不可取 。
22/3?n
1lo g?n
2009-7-27
假设元素的比较与 i和 j的比较时间相同（整型数）。又设
case语句中仅需一次 i和 j的比较就能够确定是哪种情况。记此时 MAXMIN的频率计数为 C(n),n=2k (k为正整数）。则有，
2 n=2
C(n) =
2C(n/2)+3 n>2
化简得，
C(n) = 2C(n/2) + 3
= …
= 5n/2 -3
按照同样的假设，重新估算 STRAITMAXMIN算法的比较次数为,3(n-1)。
考虑 MAXMIN算法 递归调用的开销,此时 MAXMIN算法的效率可能还不如 STRAITMAXMIＮ算法。
2009-7-27
结论：如果 A中的元素间的比较代价远比整型数
（下标）的比较 昂贵,则分治方法将产生一个 效率较高 的算法；
反之，可能仅得到一个 低效 的算法。
故，分治策略只能看成一个 较好的 但 并不总是成功的算法设计指导。
2009-7-27
2.4 归并分类
1,分类问题 ——排序给定一 n个元素的集合 A，按照某种方法将 A中的元素按非降或非增次序排列。
分类：内排序，外排序常见内排序方法：冒泡排序插入排序归并排序快速排序堆排序
…
[例 ]
输入,（ 8,5,4,9）
输出：（ 4,5,8,9）
或 （ 9,8,5,4）
2009-7-27
2,插入分类算法 2.7 插入分类
procedure INSERTIONSORT(A,n)
//将 A(1,n)中的元素按非降次序分类,n≥1//
A(0)← -∞//设置初始边界值
for j←2 to n do //A(1:j -1)已分类 //
item←A(j);i←j -1
while item<A(i) do //0≤i<j//
A(i+1)←A(i); i←i -1
repeat
A(i+1) ←item;
repeat
end INSERTIONSORT
(8,5,4,9)
(8,5,4,9)
(5,8,4,9)
(5,8,4,9)
(4,5,8,9)
(4,5,8,9)
2009-7-27
插入分类算法示例
(-∞,8,5,4,9)j=2 i=1 item=5
item < A(i),执行 while得 (-∞,8,8,4,9) i=0
item > A(i),跳出 while循环
(-∞,5,8,4,9)j=3 i=2 item=4
item < A(i),执行 while得 (-∞,5,8,8,9) i=1
item < A(i),执行 while得 (-∞,5,5,8,9) i=0
item > A(i),跳出 while循环
(-∞,4,5,8,9)j=4 i=3 item=9
item > A(i),跳出 while循环 ……
2009-7-27
性能分析：以比较为基础最坏 情况：输入数据按非增次序排列,每次 内层
while循环比较 执行 j次（ j=2,3,…,n) 。则有，
最好 情况：输入数据已按非降序排列，不进入
while循环，则最好情况下计算时间为 Ω(n)
)Θ (n 2?
nj2
1 - 1 ) ) / 2( n ( nj
2009-7-27
3.分治策略求解基本设计思想：将原始数组 A中的元素分成两个子集合,A1(1,)和 A2( +1,n)。分别对这两个子集合单独分类，然后将已分类的两个子序列归并成一个含有 n个元素的分类好的序列。
这样的一个分类过程称为 归并分类 。
n/2n/2
2009-7-27
归并分类示例
设 A=（ 310,285,179,652,351,423,861,254,450,520）
1）划分过程
310,285,179,652,351,423,861,254,450,520
310,285,179,652,351 423,861,254,450,520
310,285,179 652,351
310,285 179
310 285
652 351
423,861,254 450,520
423,861 254
423 861
450 520
2009-7-27
2）归并过程首先进入左分枝的划分与归并。首先形成的划分状态是：
（ 310 |||| 285 ||| 179 || 652,351 | 423,861,254,450,520）
第一次归并：（ 285,310 ||| 179 || 652,351 | 423,861,254,450,520）
第二次归并：（ 179,285,310 || 652,351 | 423,861,254,450,520）
第三次归并：（ 179,285,310 || 351,652 | 423,861,254,450,520）
第四次归并：（ 179,285,310,351,652 | 423,861,254,450,520）
进入右分枝的划分与归并过程
（略）
2009-7-27
3）用树结构描述归并分类过程
2009-7-27
算法 2.8 归并分类
procedure MERGESORT(low,high)
//A(low:high)是一个全程数组，它含有 high-low+1≥0 个待分类的元素 //
integer low,high
if low<high then
mid← //计算 中分点 //
call MERGESORT(low,mid) //在第一个子集合上分类 (递归 )//
call MERGESORT(mid+1,high) //在第二个子集合上分类 (递归 )//
call MERGE(low,mid,high) //归并已分类的两子集合 //
endif
end MERGESORT
h ig h ) / 2( lo w?
2009-7-27
算法 2.9 使用辅助数组归并两个已分类的集合
procedure MERGE(low,mid,high)
//A(low,high)是一个全程数组,它含有两个放在 A(low,mid)和 A(mid+1,high)中的已分类的子集合,目标是将这两个已分类的集合归并成一个集合，并存放到 A(low,high)中 //
integer h,I,j,k,low,mid,high;//low≤mid＜ high//
global A(low,high);local B(low,high)
h←low;i←low; j←mid+1;
while h≤mid and j≤high do //当两个集合都没有取尽时,将较小的元素先存放到 B中 //
if A(h)≤A(j) then B(i) ←A(h);h←h+1 //如果前一个数组中的元素较小 //
else B(i) ←A(j); j←j+1 //如果后一个数组中的元素较小 //
endif
repeat
//处理尚有剩余元素的集合 //
if h>mid then for k←j to high do B(i) ←A(k);i←i+1; repeat
else for k←h to mid do B(i) ←A(k);i←i+1; repeat
endif
for k ←low to high do A(k) ←B(k) repeat //将已归并的集合复制到 A中 //
end MERGE
2009-7-27
Merge算法示例
(4,5,8,9)|(1,2,6,7)? (1,2,4,5,6,7,8,9)
参数,low = 1; high = 8; mid = 4
(4,5,8,9)|(1,2,6,7)
h j j j jh h
(1 42 5 6 7 8 9)
j
2009-7-27
性能分析
1) 过程 MERGE的归并时间与两数组元素的总数成正比
(可表示为,cn,n为元素数,c为某正常数 )
2) 过程 MERGESORT的分类时间用递推关系式表示如下,
a n=1,a是常数
T(n)=
2T(n/2)+cn n>1,c是常数化简,若 n=2k,则有,
T(n) =2(2T(n/2^2)+cn/2)+cn
= 2^2T(n/2^2) + 2cn =2^2(2T(n/2^3) +cn/2^2) + 2cn
= 2^3T(n/2^3)+3cn = …
=2kT(1)+kcn
=an+cnlogn //k=logn//
若 2k<n<2k+1,则有 T(n)≤T(2k+1)。
所以得,T(n) = Ο(nlogn)
2009-7-27
4,归并分类算法的改进
1）算法 2.8存在的问题
递归层次太深在 MERGESORT的执行过程中，当集合仅含有两个元素时，仍要进一步做递归调用，直至每个集合仅含有一个元素时才退出递归调用。
在集合含有仅相当少的元素时，较深层次的递归调用使得时间 过多地消耗 在处理递归上。
元素在数组 A和辅助数组 B之间的频繁移动每次归并，都要首先将 A中的元素移到 B中，在由 B复制到 A的对应位置上。
2009-7-27
2）改进措施
针对递归层次问题采用能 在小规模集合 上有效工作的其它算法，直接对小规模集合处理。
如 INSERTIONSORT算法
针对元素频繁移动问题采用一个称为 链接信息数组 LINK（ 1,n） 的数据结构，
记录归并过程中 A中的元素相对于其排序后在分类表中 位置坐标的链接关系。
LINK(i)取值于 [1,n]，是指向 A的元素的指针：在分类表中它指向下一个元素在 A中的位置坐标。
2009-7-27
例：
LINK (1) (2) (3) (4) (5) (6) (7) (8)
6 4 7 1 3 0 8 0
该表中含有 两个子表,0表示表的结束。
设置 表头指针 Q和 R分别指向两个子表的起始处：
Q=2,R=5；
则有，
表 1,Q(2,4,1,6),经过分类后有,A(2)≤ A(4) ≤ A(1) ≤ A(6)
表 2,R(5,3,7,8),同样有,A(5)≤ A(3) ≤ A(7) ≤ A(8)
链接信息表在归并过程中的应用,
将归并过程中元素在 A和 B之间移动的过程变成更改 LINK
所指示的链接关系，从而避免移动元素的本身。
分类表可以通过 LINK的表头指针和读取 LINK中的链接关系取得。
2009-7-27
改进后的归并分类模型算法 2.10 使用链接信息数组的归并分类模型
procedure MERGESORT1(low,high,p)
//利用链接信息数组 LINK(1:n)将全程数组 A(low:high)按非降次序分类。 LINK中值表示按分类次序给出
A下标的表，并把 p置于该表的开始处 //
global A(low:high),LINK(low,high)
if high-low+1<16 //当集合中的元素个数足够少 (<16)时，采用更有效的小规模集合上的分类算法直接分类 //
then call INSERTSORT1(A,LINK,low,high,p) //算法 2.7的改型 //
else mid←
call MERGESORT1(low,mid,q) //返回 q表 //
call MERGESORT1(mid+1,high,r) //返回 r表 //
call MERGE1(q,r,p) //将表 q和表 r归并成表 p//
endif
end MERGESORT1
h ig h ) / 2( lo w?
2009-7-27
算法 2.11 使用链接表归并已分类的集合
procedure MERGE1(q,r,p)
//q和 r是全程数组 LINK(1:n)中两个表的指针。归并这两个表，得到一个由 p所指示的新表。此表将
A中的元素按非降次序分类。 LINK(0)被定义 //
global n,A(1:n),LINK(1:n)
local integer i,j,k
i←q;j←r;k←0 //新表在 LINK(0)处开始 //
while i≠0 and j≠0 do //当两表均非空时 //
if A(i) ≤ A(j) //找较小的关键字 //
then LINK(k) ←i;k←i;i←LINK(i) //加一个新关键字到表中 //
else LINK(k) ←j;k←j;j←LINK(j) //加一个新关键字到表中 //
endif
repeat
if i=9 then LINK(k) = j
else LINK(k) = i
endif
end MERGE1
2009-7-27
MERGESORT1 的调用
在初次调用时，待分类的 n个元素放于 A(1:n)中。
LINK(1:n)初始化为 0；
初次调用,call MERGESORT1(1,n,p)
p作为按分类次序给出 A中元素的指示表的指针。
3）改进归并分类算法示例设元素表：（ 50,10,25,30,15,70,35,55）
采用 MERGESORT1对上述元素表分类（不做小规模集合的单独处理）
下表给出在每一次调用 MERGESORT1结束后,LINK数组的变化情况。
2009-7-27
在上表的最后一行,p=2返回，得到链表（ 2,5,3,4,7,1,8,6）
即,A(2)≤ A(5)≤ A(3)≤ A(4)≤ A(7)≤ A(1)≤ A(8)≤ A(6)
i ji j
k k k
j
k
2009-7-27
5,以比较为基础分类的时间下界任何以关键字比较为基础的分类算法，其最坏情况下的时间下界都为,Ω(nlogn)
利用 二元比较树 证明。
假设参加分类的 n个关键字 A(1),A(2),?,A(n) 互异。任意两个关键字的比较必导致 A(i)<A(j)或 A(i)>A(j)的结果。
以二元比较树描述元素间的比较过程：
若 A(i)<A(j)，进入下一级的 左分支
若 A(i)>A(j)，进入下一级的 右分支
2009-7-27
算法在 外部结点 终止。
从根到某外结点的 路径 代表某个特定输入情况下一种唯一的 分类排序序列 。
路径长度 表示生成该序列代表的分类表所需要的 比较次数。 而 最长的路径 代表算法在最坏情况下的执行情况，该路径的长度即是算法在最坏情况下所作的比较次数。
故，以比较为基础的分类算法的 最坏情况下界 等于该算法对应的比较树的 最小高度 。
2009-7-27
① 由于 n个关键字有 n!种可能的排列，所以二元比较树中将有 n!个外部结点,每种排列对应于某种特定输入情况下的分类情况，每个外部结点表示一种可能的分类序列。
② 设一棵二元比较树的所有 内结点 的级数均小于或等于 k，则该树中最多有 2k个外结点。 (引理 1.1)
记算法在最坏情况下所作的比较次数为 T(n),则有 T(n)=k,生成外结点所代表的分类序列所需的比较次数等于该外结点所在的级数 -1；
根据①和②的分析，有：
n!≤2 T(n)
化简：
当 n>1时，有 n!≥n(n -1)(n-2)?( )≥(n/2) n/2
当 n≥4 时，有 T(n)≥(n/2)log(n/2)≥(n/4)logn
故，任何以比较为基础的分类算法的最坏情况的时间下界为：
Ω(nlogn)
n/2
2009-7-27
2.5 快速分类任何一个基于比较来确定两个元素相对位置的排序算法需要 Ω(nlogn) 计算时间。如果我们能设计一个需要 O(n1ogn)时间的排序算法，则在渐近的意义上，这个排序算法就是最优的。许多排序算法都是追求这个目标。
下面介绍快速排序算法，它在平均情况下需要 O(nlogn)时间。这个算法是由 C.A.R.Hoare发明的。
1,问题描述分类问题
2.划分
快速分类是一种基于 划分 的分类方法；
划分,选取待分类集合 A中的某个元素 t，按照与 t的大小关系重新整理 A中元素，使得整理后的序列中所有在 t以前出现的元素均 小于等于 t，而所有出现在 t以后的元素均 大于等于 t。这一元素的整理过程称为 划分 （ Partitioning）。元素 t称为 划分元素 。
快速分类,通过反复地对待排序集合 进行划分 达到分类目的的分类算法。
2009-7-27
划分过程（ PARTITION）的算法描述算法 2.2 用 A(m)划分集合 A(m:p-1)
procedure PARTITION(m,p)
integer m,p,i; global A(m:p-1)
v←A(m);i←m //A(m) 是划分元素 //
loop
loop i←i+1 until A(i)≥v repeat // i 由左向右移 //
loop p←p -1 until A(p)≤v repeat //p由右向左移 //
if i<p then
call INTERCHANGE(A(i),A(p))
else exit
endif
repeat
A(m)←A(p) ； A(p)←v // 划分元素在位置 p//
end PARTITION
2009-7-27
注：
算法对集合 A(m:p-1)进行划分。并使用待划分区间的第一个元素 A(m)作为划分元素
A(p)不在划分区间内，但被定义，且 A(p） ≥ A(m)，用于限界
2009-7-27
例 2.5 划分实例
(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) i p
A,65 70 75 80 85 60 55 50 45 +∞ 2 9
|……………………………………|
A,65 45 75 80 85 60 55 50 70 +∞ 3 8
|…………………………|
A,65 45 50 80 85 60 55 75 70 +∞ 4 7
|………………|
A,65 45 50 55 85 60 80 75 70 +∞ 5 6
|……|
A,65 45 50 55 60 85 80 75 70 +∞ 6 5
|……………………|
A,60 45 50 55 65 85 80 75 70 +∞
划分元素定位于此交换划分元素
2009-7-27
经过一次,划分” 后，实现了对集合元素的调整：其中一个子集合的所有元素 均小于 等于另外一个子集合的所有元素。
按同样的策略对两个子集合进行分类处理。当子集合分类完毕后，整个集合的分类也完成了。这一过程避免了子集合的归并操作。这一分类过程称为快速分类 。
2009-7-27
3.快速分类通过反复使用划分过程 PARTITION实现对集合元素分类的算法。
算法 2.13 快速分类
procedure QUICKSORT(p,q)
//将数组 A(1:n)中的元素 A(p),…A(q) 按递增的方式分类。
A(n+1)有定义，且假定 A(n+1)←+ ∞//
integer p,q;global n,A(1:n)
if p<q then
j←q+1 //进入时,A(j)定义了划分区间 [p,q]的 上界,初次调用时 j=n+1
call PARTITION(p,j) //出口时,j待出此次划分后划分元素所在的 坐标位置 //
call QUICKSORT(p,j-1) //前一子集合上递归调用
call QUICKSORT(j+1,q) //后一子集合上递归调用
endif
end QUICKSORT
2009-7-27
4,快速分类分析
统计的对象：元素的 比较次数,记为,C(n)
两点假设
① 参加分类的 n个元素各不相同
② PARTITION中的划分元素 v是 随机 选取的（针对平均情况的分析）
随机选取划分元素,
在划分区间 [m,p]随机生成某一坐标,i←RANDOM(m.p -1)；
调换 A(m)与 A(i):v←A(i);A(i) ←A(m);i←m
作用：将随机指定的划分元素的值依旧调换到 A(m)位置。
之后，算法主体不变，仍从 A(m)开始执行划分操作。
2009-7-27
递归层次
QuickSort(1,n)
QuickSort(1,j1-1) QuickSort(j1-1,n)
QuickSort(1,j21-1) QuickSort(j21+1,j1-1) QuickSort(j1-1,j22-1) QuickSort(j22+1,n)
n个元素参加划分和分类去掉 1个第一级的划分元素
n-1个元素参加划分和分类去掉 2个第二级的划分元素
n-3个元素参加划分和分类去掉 4个第三级的划分元素第一层第二层第三层设在任一级递归调用上，调用 PARTITION处理的所有元素总数为 r，则，初始时 r=n，以后的每级递归上，由于删去了上一级的划分元素，故 r比上一级至少 1：
理想情况,第一级少 1，第二级少 2，第三级少 4,… ；
最坏情况,每次仅减少 1（如集合元素已经按照递增或递减顺序排列）
2009-7-27
最坏情况分析
记 最坏情况 下的元素比较次数是 Cw(n)；
PARTITION一次调用中的元素比较数是 p-m+1,故每级递归调用上，元素的比较次数等于该级所处理的待分类元素数。
最坏情况下，每级递归调用的元素总数仅比上一级少 1，
故 Cw(n)是 r由 n到 2的累加和。
即,Cw(n)= = Ο(n2)?
nr
r
2
2009-7-27
平均情况分析平均情况 是指集合中的元素以任一一种顺序排列，且任选所有可能的元素作为划分元素进行划分和分类，在这些所有可能的情况下，算法执行性能的 平均值 。
设调用 PARTITION(m,p)时，所选取划分元素 v恰好是
A(m:p-1)中的第 i小元素（ 1≤i≤p -m）的概率相等。则经过一次划分，所留下的待分类的两个子文件恰好是 A(m:j-1)和
A(j+1:p-1)的概率是,1/(p-m),m≤j<p 。则有，
其中，
n+1是 PARTITION第一次调用时所需的元素比较次数。
CA(0) = CA(1) = 0
nk AAnA knCkCnnC 11 ))()1((1)(
2009-7-27
化简上式可得：
CA(n)/(n+1) = CA(n-2)/(n-1)+2/n+2/(n+1)
= CA(n-3)/(n-2)+2(n-1)+2/n+2/(n+1)
= CA(1)/2+
由于所以得,CA(n)<2(n+1)loge(n+1) = Ο(nlogn)
13
/12
nk
k
)1(l o g/1 12
13
nk en xdx
nk
2009-7-27
5,快速分类算法的迭代模型
消去递归（略）
6,快速分类与归并分类比较两者平均情况时间都是 Ο(nlogn），平均情况下哪种快一些？
实验证明快速分类要快一些
2009-7-27
2.6 选择问题
1,问题描述给出含有 n个元素表 A(1:n)，要求确定其中的第 k小元素。
2,设计思路利用 PARTITION过程。如果划分元素 v测定在 A(j)的位置上，则有 j-1个元素小于或等于 A(j)，且有 n-j个元素大于或等于 A(j)。此时，
若 k=j，则 A(j)即是第 k小元素；否则，
若 k<j，则第 k小元素将出现在 A(1:j-1)中；
若 k>j，则第 k小元素将出现在 A(j+1:n)中。
2009-7-27
3,利用 PARTITION实现的选择算法
算法描述算法 2.15 找第 k小元素
procedure SELECT(A,n,k) //在数组 A(1:n)中找第 k小元素，并将之放在 A(k)中。 //
integer n,k,m,r,j;
m←1;r ← n+1;A(n+1) ←+∞ //A(n+1)被定义，并置为一大值，用于限界 //
loop //在进入循环时,1≤m≤k≤r≤n+1 //
j ←r //将剩余元素的最大下标加 1后置给 j //
call PARTITION(m.j) //返回 j,它使得 A(j)是第 j小的值 //
case
:k=j,return
:k<j,r←j //j是新的上界 //
:else,m←j+1 //k>j,j+1是新的下界 //
endcase
repeat
end SELECT
2009-7-27
算法分析两点假设
① A中的元素 互异
② 随机选取 划分元素，且选择 A中任一元素作为划分元素的 概率相同分析
每次调用 PARTITION（ m,j),所需的元素比较次数是
Ο(j-m+1)。
在执行一次 PARTITION后，或者找到第 k小元素，或者将在缩小的子集 (A(m,k-1)或 A(k+1,j))中继续查找。缩小的子集的元素数将 至少 比上一次划分的元素数 少 1。
2009-7-27
1) 最坏情况
SELECT的最坏情况时间是 Ο(n2)
当 A中的元素已经按照 递增 的顺序排列,且 k=n。
此时，需要 n次 调用 PARTITION过程，且每次返回的元素位置是子集中的第一个元素，子集合的元素数一次 仅减少１,而 j值不变。
则,n次调用的时间总量是
)())1(( 2
1
ni
n
2009-7-27
2) 平均情况设 是找 A(1:n)中第 k小元素的平均时间。 是
SELECT的平均计算时间，则有并定义则有,T(n)≤R(n)。
nk
k
AnA nTnT
1
1 )()(
)(nTA
k
k
A nTnR )}(m a x {)(?
)(nTkA
2009-7-27
定理 2.4 SELECT的平均计算时间 TA(n)是 Ο(n)
证明：
PARTITION和 SELECT中,case语句的执行时间是 Ο(n)。
在随机等概率选择划分元素时，首次调用 PARTITION中划分元素 v刚好是 A中第 i小元素的概率为 1/n,1≤ i≤ n。
则，存在正常数 c,c>0,有，
n≥2
且有，
n≥2
1 ) )(iTi)(nT(cn( n )T
nik
k
A
ki1
ik
An1
k
A
1 ) }(iRi)(nR{m axcnR ( n )
nikki1kn
1
( i ) }R( i )R{m axcn
1n
k
1n
1knk
n
1
2009-7-27
令 c≥R(1) 。利用 数学归纳法 证明，对所有 n≥2,有 R(n)≤4cn.
① 当 n=2时，由上式得：
② 假设对所有得 n,2≤n<m,有 R(n)≤4cn
③ 当 n = m时，有，
由于 R(n)是 n的非降函数，故在当 m为偶数而 k=m/2，或当 m为奇数而 k=(m+1)/2时,取得极大值。因此，
若 m为偶数,则若 m为奇数,则由于 TA(n)≤R(n),所以 TA(n)≤4cn 。 故,TA(n)=Ο(n)
R ( 1 ) }m a x { R ( 1 ),212cR ( n )
4 c n2,5 c
( i ) }R( i )R{m axcm)( 1m
k
1m
1kmkm
1
nR
1m
m / 2
m2 R ( i)cmR ( m )?
1m
m / 2
m
8c 4 cmicm
1m
1 ) / 2(m
m
2 R ( i )cmR ( m )?
1m
1 ) / 2(m
m
8c 4 cmicm
( i)R( i)R 1n
k
1n
1kn
2009-7-27
4,最坏情况是 Ο(n)的选择算法
1）采用两次取中间值的规则精心选取划分元素首先，将参加划分的 n个元素分成 组，每组有 r个元素 (r≥1) 。（多余的 个元素忽略不计）
然后，对这 组每组的 r个元素进行分类并找出其中间元素 mi,1≤i≤,共得 个中间值。
之后，对这 个中间值分类，并找出其中间值 mm。
将 mm作为划分元素执行划分。
2）算法描述
n/r
n/rrn?
n/r
n/rn/r
n/r
2009-7-27
算法 2.16 使用 二次取中规则 得选择算法的说明性描述
//在集合 A中找第 k小元素，使用两次取中规则 //
① 若 n≤r，则采用 插入法 直接对 A分类并返回第 k小元素
② 把 A分成大小为 r的 个子集合，忽略多余的元素
③ 设 M={m1,m2,…m } 是 子集合的 中间值集合
④ v←SELECT2(M,,)
⑤ j← PARTITION(A,v) //v作为划分元素，划分后 j等于划分元素所在位置的下标 //
⑥ case
:k=j,return(v)
:k<j,设 S是 A(1:j-1)中元素的集合
return(SELECT2(S,k,j-1))
:else,设 R是 A(j+1:n)中元素的集合
return(SELECT2(R,k-j,n-j))
endcase
end SELECT2
n/r
n/r
n/r2/n/r
2009-7-27
例：设 n=35,r=7。
分为 n/r = 5个元素组,B1,B2，
B3,B4,B5；每组有 7个元素。
B1-B5按照各组的 mi的非增次序排列。
mm = mi的中间值,1≤i≤5
由图所示有,
mm
中间值小于等于 mm的元素大于等于 mm的元素非降次序
B1 B2 B3 B4 B5
按照 mi的非降次序排列
2009-7-27
由于 r个元素的 中间值 是第 小元素。则，
至少有 个 mi小于或等于 mm；
至少有 个 mi大于或等于 mm。
则，至少有 个元素小于或等于（或大于或等于） mm。
当 r=5，则使用两次取中间值规则来选择 v=mm，可推出，
至少有 个元素小于或等于选择元素 v。
至多有 个元素大于 v。
至多有 0.7n+1.2个元素小于 v。
故，这样的 v可 近似平均 地划分 A中的 n个元素。
/2n / r1/2n / rn / r
2/n/r
2/r
/2n /rr/2
n/55.1
1,20,7 nn / 51,5n
2009-7-27
2) 算法分析记 T(n)是 SELECT2所需的最坏情况时间对特定的 r分析 SELECT2:选取 r=5。
假定 A中的元素各不相同，则有
① 若 n≤r，则采用插入法直接对 A分类并返回第 k小元素 → Ο(1)
② 把 A分成大小为 r的 个子集合，忽略多余的元素 → Ο(n)
③ 设 M={m1,m2,…m } 是 子集合的中间值集合 → Ο(n)
④ v←SELECT2(M,,) → T(n/5)
⑤ j← PARTITION(A,v) → Ο(n)
⑥ case →T(3n/4),n ≥24
:k=j,return(v)
:k<j,设 S是 A(1:j-1)中元素的集合 ; return(SELECT2(S,k,j-1))
:else,设 R是 A(j+1:n)中元素的集合 ; return(SELECT2(R,k-j,n-j))
endcase
end SELECT2
n/r
n/r
n/r2/n/r
2009-7-27
故有，
cn n ＜ 24,
T(n)＝
T(n/5)+T(3n/4)+cn n≥24
用归纳法可证：
T(n)≤20cn
即,T(n) = Ο(n)
2009-7-27
当 A中的元素 不尽相同步骤⑤经 PARTITION调用所产生的 S和 R两个子集合中可能存在一些元素 等于 当前的划分元素 v,可能导致 |S|或 |R|大于 0.7n+1.2。
此时上述处理 作一下改进：
方法一：将 A集合分成 3个子集合 U,S和 R，其中 U是有 A中所有与 v相同的元素组成,S是由 A中所有比 v小的元素组成,R则是 A中所有比 v大的元素组成。
同时步骤⑥更改：
case
:|S|≥k:return(SELECT2(S,k,|S|)
:|S|+|U|≥k:return(v)
:else,return(SELECT2(R,k-|S|-|U|,|R|))
endcase
从而保证 |S|+|R|≤0.7n+1.2 成立，故关于 T(n)的分析仍然成立。
T(n) = Ο(n)
2009-7-27
方法二：选取其他的 r值进行计算特例：当 r=5,且 A中的元素不尽相同。假设其中有 0.7n+1.2个元素比 v小而其余的元素都等于 v的情况。
则，经过 PARTITION，在这些等于 v的元素中至多有一半可能在 S中，故
|S|≤0.7n+1.2+(0.3n -1.2)/2=0.85n+0.6
同理,|R|≤0.85n+0.6
可得，步骤④和⑥此时所处理的元素总数将是
1.05n+0.6>n
不再是线性关系。故有 T(n)≠ Ο(n)
改进：
取 r=9。经计算可得，此时将有 个元素小于或等于 v，同时至少有同样多的元素大于或等于 v。
则当 n≥90 时,|S|和 |R|都至多为基于上述分析，有新的递推式：
n/92.5
72/6325.136/319/25.1)9/5.2(9/5.2 21 nnnnnnn
2009-7-27
故有，
c1n n＜ 90
T(n) ＝
T(n/9)+T(63n/72)+c1n n≥90
用归纳法可证：
T(n)≤72c1n
即,T(n) = Ο(n)
2009-7-27
SELECT2的实现
算法中需要解决的两个问题
如何确定子集合的中间值
当 r较小时，采用 INSERTIONSORT(A,i,j)直接对每组的 r个元素分类，在分类好的序列中，中间元素即为当前 r个元素的中间值。
如何保存 个子集合的中间值
注：各组找到的中间元素值将存放数组 A的前部
n/r
2009-7-27
算法 2.17SELECT2的 SPARKS的描述
procedure SEL(A,m,p,k)
//返回一个 i，使得 i∈[m,p],且 A(i)是 A(m:p)中第 k小元素,r是一个全程变量，其取值为大于
1的整数
global r; integer n,i,j
if p-m+1≤r then call INSERTIONSORT(A,m,p); return (m+k -1); endif
loop
n←p -m+1 //元素数 //
for i←1 to do // 计算中间值 //
call INSERTIONSORT(A,m+(i-1)*r,m+i*r-1) //将中间值收集到 A(m:p)的前部 //
call INTERCHANGE(A(m+i-1),A(m+(i-1)r + -1))
repeat
j←SEL(A,m,m+ -1,)//mm//
call INTERCHANGE(A(m),A(j)) //产生划分元素 //
j←p+1
call PARTITION(m,j)
case
:j-m+1=k,return(j)
:j-m+1>k,p←j -1
:else,k←k -(j-m+1);m←j+1
endcase
repeat
end SEL
n/r
n/r/2n/r
r/2
2009-7-27
2.7斯特拉森矩阵乘法矩阵乘法是线性代数中最常见的运算之一，它在数值计算中有广泛的应用。若 A和 B是 2个 n× n的矩阵，则它们的乘积 C=AB同样是一个 n× n的矩阵。 A和 B的乘积矩阵 C中的元素 C[i,j]定义为,
若依此定义来计算 A和 B的乘积矩阵 C，则每计算 C的一个元素 C[i,j]，需要做 n个乘法和 n-1次加法。因此，求出矩阵 C的 n2个元素所需的计算时间为
0(n3)。
2009-7-27
60年代末,Strassen采用了分治技术，将计算 2个 n阶矩阵乘积所需的计算时间改进到
O(nlog7)=O(n2.81)。
首先，我们还是需要假设 n是 2的幂。将矩阵
A,B和 C中每一矩阵都分块成为 4个大小相等的子矩阵，每个子矩阵都是 n/2× n/2的方阵。由此可将方程 C=AB重写为,
2009-7-27
由此可得,
C11=A11B11+A12B21
C12=A11B12+A12B22
C21=A21B11+A22B21
C22=A21B12+A22B22
如果 n=2，则 2个 2阶方阵的乘积可以直接用上式计算出来，共需 8次乘法和 4次加法。当子矩阵的阶大于 2时，为求 2个子矩阵的积，可以继续将子矩阵分块，直到子矩阵的阶降为 2。这样，就产生了一个分治降阶的递归算法
2009-7-27
分治法的计算时间耗费 T(n)应该满足：
这个递归方程的解仍然是 T(n)=O(n3)。因此，
该方法并不比用原始定义直接计算更有效。
究其原因，乃是由于没有减少矩阵的乘法次数。而矩阵乘法耗费的时间要比矩阵加减法耗费的时间多得多。要想改进矩阵乘法的计算时间复杂性，必须减少子矩阵乘法运算的次数。
2009-7-27
Strassen提出了一种新的算法来计算 2个 2阶方阵的乘积。他的算法只用了 7
次乘法运算，但增加了加、减法的运算次数
P=(A11+A22)(B11+B22)
Q=(A21+A22)B11 R=A11(B12-B22)
S=A22(B21-B11) T=(A11+A12)B22
U=(A21-A11)(B11+B12)
V=(A12-A22)(B21+B22)
用八个加减法计算 Cij
C11=P+S-T+V C12=R+T
C21＝ Q+S C22=P+R-Q+U
共用 7次乘法和 18次加减法按照解递归方程的套用公式法，其解为 T(n)=O(nlog7)≈O(n2.81)。
2009-7-27
有人曾列举了计算 2个 2阶矩阵乘法的 36种不同方法。但所有的方法都要做 7次乘法。除非能找到一种计算 2阶方阵乘积的算法，使乘法的计算次数少于 7次，按上述思路才有可能进一步改进矩阵乘积的计算时间的上界。但是 Hopcroft 和
Kerr(197l) 已经证明，计算 2个 2× 2矩阵的乘积,7次乘法是必要的。
因此，要想进一步改进矩阵乘法的时间复杂性，就不能再寄希望于计算 2× 2矩阵的乘法次数的减少。或许应当研究
3× 3或 5× 5矩阵的更好算法。在 Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.367)。而目前所知道的矩阵乘法的最好下界仍是它的平凡下界 Ω(n2)。
第二章 分治法
——―分”而治之
2.1 一般方法
对大规模问题的求解
利用分治法求解大规模问题
1.基本思想分而治之方法法与软件设计的模块化方法非常相似。
为解决一个大问题，可以 （ 1）把它 分解 成两个或多个更小的问题；（ 2） 分别解决 每个小问题；（ 3）把各小问题的解答 组合 起来，即可得到原问题的解。
小问题通常与原问题相似或同质,因而可以 递归 地使用分而治之策略解决。
2009-7-27
Q q 2
q k
q 1
子 问 题
.,,
a 2
a k
a 1
子 问 题 求 解
.,,
问 题
A
子 结 果合 并分 解逐 步 细 化 的 过 程通常，子问题与原始问题,同质”
2009-7-27
例 [找伪币 ] 假设 16 枚金币中有一枚是伪造的，真假金币的区别仅是重量不同 (伪币轻一些），利用一个没有砝码的天平作工具，找出这枚伪造的金币。
方法 1：比较硬币 1和 2的重量，有一个轻则找到；
否则比较硬币 3和 4，依次比较下去，直到找到。最多 8次比较。
方法 2：利用分治法。 16个硬币分为两组，每组 8个，
比较重量，伪币在轻的一组。将轻的一组再分为两组，每组 4个 …… 继续划分下去，依次每组 2个，每组 1个，此时找到。
2009-7-27
算法 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),对输入规模为 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,分治策略的抽象化控制
2009-7-27
DANDC的计算时间若所分成的两个子问题的输入规模大致相等，则 DANDC
总的计算时间可用递归关系式表示，如下：
g(n) n足够小
T(n) =
2T(n/2) + f(n) 否则注：
T(n),表示输入规模为 n的 DANDC计算时间
g(n),表示对足够小的输入规模直接求解的计算时间
f(n),表示 COMBINE对两个子区间的子结果进行合并的时间
（该公式针对具体问题有各种不同的变形）
2009-7-27
2.2 二分检索（折半查找）
1,问题的描述已知一个按 非降次序 排列的元素表 a1,
a2,…,a n,判定某给定的元素 x是否在该表中出现。
若是，则找出 x在表中的位置并返回其所在下标
若非，则返回 0值。
2009-7-27
分治求解策略分析,
定义问题的 形式描述,I=(n,a1,a2,…,a n,x)
问题分解：选取下标 k，由此将 I分解为 3个子问题：
I1=(k-1,a1,a2,…,a k-1,x)
I2=(1,ak,x)
I3=(n-k,ak+1,a2,…,a n,x)
对于 I2，若 ak=x，则有解 k，对 I1,I3不用再求解；否则，
若 x<ak，则只在 I1中求解，对 I3不用求解；
若 x>ak，则只在 I3中求解，对 I1不用求解；
I1,I3上的求解可再次采用分治方法划分后求解（ 递归过程 ）
2009-7-27
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
:x<A(mid):high←mid -1
:x>A(mid):low ←mid+1
:else:j←mid;return
endcase
repeat
end BINSRCH
h ig h ) / 2( lo w?
注,
给定一个按非降次序排列的元素数组 A(1:n)，
n≥1,判断 x是否出现。
若是，置 j，使得 x=A(j)
若非,j=0
2009-7-27
例 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 找不到 找到找到成功 的检索 不成功 的检索 成功 的检索
2009-7-27
3,算法的正确性证明定理 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，算法终止；
或 x<A(mid)，置 high←mid -1，搜索范围实际缩小为 [low,mid-1]，
进入下次循环，对 [mid+1,high]区间不做进一步搜索；
或 x>A(mid)，置 low←mid+1,进入下次循环；搜索范围实际缩小为 [mid+1,high]，对 [low,mid-1]区间不做进一步搜索；
因 low,high,mid都是整型变量，故按照上述规则，在 有限步内,或找到某个 mid，有 A(mid) = x；或变得 low>high，在 A中没有找到任何元素等于 x，算法终止。
2009-7-27
4,性能分析
1）空间特性
n+5个空间位置 ——О(n)
2) 时间特性区分以下情况，并进行相应的分析
成功检索,所检索的 x出现在 A中。
成功检索情况共有 n种,x恰好是 A中的某个元素,A中共有 n个元素，故有 n
种可能的情况
不成功检索,所检索的 x不出现在 A中。
不成功检索情况共有 n+1种,x<A(1),或 A(i)<x<A(i+1),1≤i<n -1或 x>A(n)
成功 /不成功检索的最好情况,执行步数最少，计算时间最短
成功 /不成功检索的最坏情况,执行步数最多，计算时间最长
成功 /不成功检索的平均情况,一般情况下的计算时间
2009-7-27
实例分析（例 2.1）
频率计数特征
1,while循环体外语句的频率计数为 1
2,集中考虑 while循环中的 x与 A中元素的比较（其它运算的频率计数与之有相同的数量级）
假定只需一次比较就可确定 case语句控制是三种情况的哪一种。查找每个元素所需的元素比较次数统计如下：
A ⑴ ⑵ ⑶ ⑷ ⑸ ⑹ ⑺ ⑻ ⑼
元素 -15 -6 0 7 9 23 54 82 101
成功检索 比较次数 3 2 3 4 1 3 2 3 4
不成功检索 比较次数 3 3 3 4 4 3 3 3 4 4
2009-7-27
成功检索最好,1次最坏,4次平均,（ 3+2+3+4+1+3+2+3+4） /9≈ 2.77次
不成功检索最好,3次最坏,4次平均,(3+3+3+4+4+3+3+3+4+4)/10 = 3.4次
2009-7-27
二元比较树
算法执行过程的 主体 是 x与一系列中间元素 A(mid)比较。可用一棵二元树描述这一过程，
并称之为 二元比较树 。
构造,比较树由称为 内结点 和外结点 的两种结点组成：
内结点,表示一次元素比较，
用圆形结点表示，存放一个
mid值；代表一次成功检索；
外结点,在二分检索算法中表示一种不成功检索的情况，用方形结点表示。
路 径,表示一个元素的比较序列。
例 2.1的二元比较树
5
2 7
1 3 6
8
4
9
2009-7-27
基于二元比较树的分析
若 x在 A中出现，则算法的执行过程在一个圆形的 内结点 处结束。
若 x不在 A中出现，则算法的执行过程在一个方形的 外结点 处结束
——外结点不代表元素的比较，因为比较过程在该外结点的上一级的内结点处结束。
5
2 7
1 3 6
8
4
9
例 2.1的二元比较树
2009-7-27
定理 2.2 若 n在区域 [2k-1,2k)中，则对于 一次成功的检索,BINSRCH至多做 k次比较；对于 一次不成功的检索,或者做 k-1次比较，或者做 k
次比较。
证明：
要点：
成功检索都在内结点处结束，不成功检索都在外结点处结束
当 2k-1≤n< 2k时，所有内结点在 1至 k级，所有外结点在第 k级或第 k+1级，
故：成功检索在 i级终止所需要的元素比较次数是 i
不成功检索在 i级外部结点终止的元素比较次数是 i-1
2009-7-27
BINSRCH计算复杂度的理论分析
1）不成功检索的最好、最坏和平均情况的计算时间均为 ——外结点处在最末的两级上；
2）最好情况下的成功检索的计算时间为最坏情况下的成功检索的计算时间为
Θ (log n)
Θ(1)
Θ (log n)
2009-7-27
3）平均情况下的成功检索的计算时间分析利用 外部结点和内部结点到根距离和之间的关系 进行推导：
记，
由根到所有内结点的距离之和称为 内部路径长度,记为 I；
由根到所有外部结点的距离之和称为 外部路径长度,记为 E。
则有,E=I+2n
记，
U(n)是平均情况下不成功检索的计算时间，则 U(n) = E/(n+1)
S(n)是平均情况下成功检索的计算时间，则 S(n) = I/n+1
利用上述公式，可有,S(n) = (1+1/n)U(n) -1
当 n→∞,S(n) ∝ U(n),而 U(n) =
所以 S(n) =
Θ (log n)
Θ (log n)
2009-7-27
4,以比较为基础检索的时间下界问题,设 n个元素的数组 A(1:n)有 A(1)< A(2) < …<
A(n)。检索一给定元素 x是否在 A中出现。
定理 2.2给出了二分检索算法的时间下界，是否预计还存在有以元素比较为基础的另外的检索算法，
它在最坏情况下比二分检索算法在计算时间上有 更低的数量级?
以比较为基础的算法,假定算法中只允许进行元素间的 比较,而不允许对它们实施其它运算。
2009-7-27
注：每个 内结点 表示一次元素的比较。每棵比较树中恰好含有 n个内结点，
分别与 n个不同 i值相对应；每个 外结点 对应一次不成功的检索，并恰好又 n+1个外结点对应于 n+1中不成功检索的情况。
任何以比较为基础的检索算法，其执行过程都可以用二元比较树来描述。
2009-7-27
以比较为基础的有序检索问题最坏情况的时间下界
定理 2.3 设 A(1:n)含有 n(n≥1) 个不同的元素，排序为 A(1)<
A(2) < …< A(n) 。又设用以比较为基础的算法去判断是否,则这样的任何算法在最坏情况下所需的最小比较次数 FIND(n)有：
n):A (1x?
1)l o g ( nF I N D ( n )
证明：从模拟求解检索问题算法的比较树可知,FIND(n)不大于树中由根到一个叶子的最长路径的距离。而所有树中必定有 n个内结点与 x在 A中的 n中可能的出现相对应。如果一棵二元树的所有内结点所在的级数小于或等于 k，则最多有 2k-1个内结点。故 n≤2 k-1,即
1)l o g ( nkF I N D ( n )
2009-7-27
任何一种以比较为基础的算法，在 最坏情况 下的计算时间都 不低于 Ο(logn)。因此，
不可能存在最坏情况比二分检索数量级还低的算法。
二分检索是解决检索问题的 最优 的 最坏情况 算法。
2009-7-27
2.3 找最大和最小元素问题描述：给定含有 n个元素的集合，
在其中找出最大和最小元素。
2009-7-27
1,直接找最大和最小元素算法 2.5 直接找最大和最小元素
procedure STRAITMAXMIN(A,n,max,min)
//将 A中的最大值置于 max，最小值置于 min//
Integer i,n
max←min←A(1)
for i←2 to n do
if A(i) > max then
max←A(i)
endif
if A(i) < min then
min←A(i)
endif
repeat
end STRAITMAXMIN
算法的性能：
只考虑算法中的 比较运算,以此代表算法的执行特征；
该算法最好、最坏、
平均情况下均需要做
2（ n-1)次元素比较
2009-7-27
STRAITMAXMIN算法的一种简单改进形式,
procedure STRAITMAXMIN1(A,n,max,min)
integer i,n
max←min←A(1)
for i←2 to n do
if A(i) > max then max←A(i) endif
else if A(i) < min then min←A(i) endif
repeat
end STRAITMAXMIN1
这使得，
最好情况,按 递增次序 排列，元素比较次数为 n-1次
最坏情况,按 递减次序 排列，元素比较次数为 2(n-1)次
平均情况,元素比较次数为 3(n-1)/2次
2009-7-27
2,分治求解策略记问题的一个实例为：
I = (n,A(1),…,A(n))
采用二分法将 I分成两个子集合处理
I1 = (,A(1),…,A( ))，和
I2 = (n-,A( +1),…,A(n))
则有，
MAX(I) = max(MAX(I1),MAX(I2))
MIN(I) = min(MIN(I1),MIN(I2))
采用递归的设计策略，得到以下算法：
n/2n/2
n/2n/2
2009-7-27
3,一种递归求解策略算法 2.6 递归求取最大和最小元素
procedure MAXMIN(i,j,fmax,fmin)
//A(1:n)是含有 n个元素的数组，参数 I,j是整数,1≤i,j≤n //
//该过程把 A(i:j)中的最大和最小元素分别赋给 fmax和 fmin //
integer i,j;global n,A(1:n)
case
:i=j,fmax←fmin←A(i) // 只有一个元素
:i=j-1:if A(i)<A(j) then fmax←A(j);fmin←A(i)
else fmax←A(i);fmin←A(j) // 两个元素的情况
endif
:else,mid← // 取中
call MAXMIN(i,mid,gmax,gmin)
call MAXMIN(mid +1,j,hmax,hmin)
fmax←max(gmax,hmax); fmin←min(gmin,hmin)
end case
end MAXMIN
j)/2(i?
2009-7-27
例：在 A(1:9) = (22,13,-5,-8,15,60,17,31,47)上执行算法 2.6
每个结点内的值分别是：
i,j,fmax,fmin
递归调用递归调用分解过程递归调用的返回
2009-7-27
性能分析 (T(n)表示元素比较数）
0 n=1
T(n) = 1 n=2
n>2
当 n是 2的幂时 (n=2k),化简上式有，
T(n)=2T(n/2) +2
=2(2T(n/22) + 2) + 2 = 22T(n/22 ) + 22 + 2
= 22(2T(n/23 )+2)+22+2 = 23T(n/23 )+23+22+2
=……= 2 k-1T(n/2k-1 ) +(2k-1+…+2 2+21)
= 2k-1T(2) +(2k-1+…+2 2+21)
= n/2 + (2k – 1 – 1) = n/2 + n – 2 = 3n/2 – 2
2)n / 2T()n / 2T(
2009-7-27
性能分析
1）与 STRAITMAXMIN算法相比，比较次数减少了 25%
（ 3n/2-2,2n-2)。
已经达到了以 元素比较为基础 的找最大最小元素的算法计算时间的 下界,
2）存在的问题：
空间占用量大
有 级的递归，入栈参数：
i,j,fmax,fmin和返回地址五个值。
时间可能不比预计的理想如果元素 A(i)和 A(j)的比较与 i和 j的比较 相差不大 时，算法 MAXMIN不可取 。
22/3?n
1lo g?n
2009-7-27
假设元素的比较与 i和 j的比较时间相同（整型数）。又设
case语句中仅需一次 i和 j的比较就能够确定是哪种情况。记此时 MAXMIN的频率计数为 C(n),n=2k (k为正整数）。则有，
2 n=2
C(n) =
2C(n/2)+3 n>2
化简得，
C(n) = 2C(n/2) + 3
= …
= 5n/2 -3
按照同样的假设，重新估算 STRAITMAXMIN算法的比较次数为,3(n-1)。
考虑 MAXMIN算法 递归调用的开销,此时 MAXMIN算法的效率可能还不如 STRAITMAXMIＮ算法。
2009-7-27
结论：如果 A中的元素间的比较代价远比整型数
（下标）的比较 昂贵,则分治方法将产生一个 效率较高 的算法；
反之，可能仅得到一个 低效 的算法。
故，分治策略只能看成一个 较好的 但 并不总是成功的算法设计指导。
2009-7-27
2.4 归并分类
1,分类问题 ——排序给定一 n个元素的集合 A，按照某种方法将 A中的元素按非降或非增次序排列。
分类：内排序，外排序常见内排序方法：冒泡排序插入排序归并排序快速排序堆排序
…
[例 ]
输入,（ 8,5,4,9）
输出：（ 4,5,8,9）
或 （ 9,8,5,4）
2009-7-27
2,插入分类算法 2.7 插入分类
procedure INSERTIONSORT(A,n)
//将 A(1,n)中的元素按非降次序分类,n≥1//
A(0)← -∞//设置初始边界值
for j←2 to n do //A(1:j -1)已分类 //
item←A(j);i←j -1
while item<A(i) do //0≤i<j//
A(i+1)←A(i); i←i -1
repeat
A(i+1) ←item;
repeat
end INSERTIONSORT
(8,5,4,9)
(8,5,4,9)
(5,8,4,9)
(5,8,4,9)
(4,5,8,9)
(4,5,8,9)
2009-7-27
插入分类算法示例
(-∞,8,5,4,9)j=2 i=1 item=5
item < A(i),执行 while得 (-∞,8,8,4,9) i=0
item > A(i),跳出 while循环
(-∞,5,8,4,9)j=3 i=2 item=4
item < A(i),执行 while得 (-∞,5,8,8,9) i=1
item < A(i),执行 while得 (-∞,5,5,8,9) i=0
item > A(i),跳出 while循环
(-∞,4,5,8,9)j=4 i=3 item=9
item > A(i),跳出 while循环 ……
2009-7-27
性能分析：以比较为基础最坏 情况：输入数据按非增次序排列,每次 内层
while循环比较 执行 j次（ j=2,3,…,n) 。则有，
最好 情况：输入数据已按非降序排列，不进入
while循环，则最好情况下计算时间为 Ω(n)
)Θ (n 2?
nj2
1 - 1 ) ) / 2( n ( nj
2009-7-27
3.分治策略求解基本设计思想：将原始数组 A中的元素分成两个子集合,A1(1,)和 A2( +1,n)。分别对这两个子集合单独分类，然后将已分类的两个子序列归并成一个含有 n个元素的分类好的序列。
这样的一个分类过程称为 归并分类 。
n/2n/2
2009-7-27
归并分类示例
设 A=（ 310,285,179,652,351,423,861,254,450,520）
1）划分过程
310,285,179,652,351,423,861,254,450,520
310,285,179,652,351 423,861,254,450,520
310,285,179 652,351
310,285 179
310 285
652 351
423,861,254 450,520
423,861 254
423 861
450 520
2009-7-27
2）归并过程首先进入左分枝的划分与归并。首先形成的划分状态是：
（ 310 |||| 285 ||| 179 || 652,351 | 423,861,254,450,520）
第一次归并：（ 285,310 ||| 179 || 652,351 | 423,861,254,450,520）
第二次归并：（ 179,285,310 || 652,351 | 423,861,254,450,520）
第三次归并：（ 179,285,310 || 351,652 | 423,861,254,450,520）
第四次归并：（ 179,285,310,351,652 | 423,861,254,450,520）
进入右分枝的划分与归并过程
（略）
2009-7-27
3）用树结构描述归并分类过程
2009-7-27
算法 2.8 归并分类
procedure MERGESORT(low,high)
//A(low:high)是一个全程数组，它含有 high-low+1≥0 个待分类的元素 //
integer low,high
if low<high then
mid← //计算 中分点 //
call MERGESORT(low,mid) //在第一个子集合上分类 (递归 )//
call MERGESORT(mid+1,high) //在第二个子集合上分类 (递归 )//
call MERGE(low,mid,high) //归并已分类的两子集合 //
endif
end MERGESORT
h ig h ) / 2( lo w?
2009-7-27
算法 2.9 使用辅助数组归并两个已分类的集合
procedure MERGE(low,mid,high)
//A(low,high)是一个全程数组,它含有两个放在 A(low,mid)和 A(mid+1,high)中的已分类的子集合,目标是将这两个已分类的集合归并成一个集合，并存放到 A(low,high)中 //
integer h,I,j,k,low,mid,high;//low≤mid＜ high//
global A(low,high);local B(low,high)
h←low;i←low; j←mid+1;
while h≤mid and j≤high do //当两个集合都没有取尽时,将较小的元素先存放到 B中 //
if A(h)≤A(j) then B(i) ←A(h);h←h+1 //如果前一个数组中的元素较小 //
else B(i) ←A(j); j←j+1 //如果后一个数组中的元素较小 //
endif
repeat
//处理尚有剩余元素的集合 //
if h>mid then for k←j to high do B(i) ←A(k);i←i+1; repeat
else for k←h to mid do B(i) ←A(k);i←i+1; repeat
endif
for k ←low to high do A(k) ←B(k) repeat //将已归并的集合复制到 A中 //
end MERGE
2009-7-27
Merge算法示例
(4,5,8,9)|(1,2,6,7)? (1,2,4,5,6,7,8,9)
参数,low = 1; high = 8; mid = 4
(4,5,8,9)|(1,2,6,7)
h j j j jh h
(1 42 5 6 7 8 9)
j
2009-7-27
性能分析
1) 过程 MERGE的归并时间与两数组元素的总数成正比
(可表示为,cn,n为元素数,c为某正常数 )
2) 过程 MERGESORT的分类时间用递推关系式表示如下,
a n=1,a是常数
T(n)=
2T(n/2)+cn n>1,c是常数化简,若 n=2k,则有,
T(n) =2(2T(n/2^2)+cn/2)+cn
= 2^2T(n/2^2) + 2cn =2^2(2T(n/2^3) +cn/2^2) + 2cn
= 2^3T(n/2^3)+3cn = …
=2kT(1)+kcn
=an+cnlogn //k=logn//
若 2k<n<2k+1,则有 T(n)≤T(2k+1)。
所以得,T(n) = Ο(nlogn)
2009-7-27
4,归并分类算法的改进
1）算法 2.8存在的问题
递归层次太深在 MERGESORT的执行过程中，当集合仅含有两个元素时，仍要进一步做递归调用，直至每个集合仅含有一个元素时才退出递归调用。
在集合含有仅相当少的元素时，较深层次的递归调用使得时间 过多地消耗 在处理递归上。
元素在数组 A和辅助数组 B之间的频繁移动每次归并，都要首先将 A中的元素移到 B中，在由 B复制到 A的对应位置上。
2009-7-27
2）改进措施
针对递归层次问题采用能 在小规模集合 上有效工作的其它算法，直接对小规模集合处理。
如 INSERTIONSORT算法
针对元素频繁移动问题采用一个称为 链接信息数组 LINK（ 1,n） 的数据结构，
记录归并过程中 A中的元素相对于其排序后在分类表中 位置坐标的链接关系。
LINK(i)取值于 [1,n]，是指向 A的元素的指针：在分类表中它指向下一个元素在 A中的位置坐标。
2009-7-27
例：
LINK (1) (2) (3) (4) (5) (6) (7) (8)
6 4 7 1 3 0 8 0
该表中含有 两个子表,0表示表的结束。
设置 表头指针 Q和 R分别指向两个子表的起始处：
Q=2,R=5；
则有，
表 1,Q(2,4,1,6),经过分类后有,A(2)≤ A(4) ≤ A(1) ≤ A(6)
表 2,R(5,3,7,8),同样有,A(5)≤ A(3) ≤ A(7) ≤ A(8)
链接信息表在归并过程中的应用,
将归并过程中元素在 A和 B之间移动的过程变成更改 LINK
所指示的链接关系，从而避免移动元素的本身。
分类表可以通过 LINK的表头指针和读取 LINK中的链接关系取得。
2009-7-27
改进后的归并分类模型算法 2.10 使用链接信息数组的归并分类模型
procedure MERGESORT1(low,high,p)
//利用链接信息数组 LINK(1:n)将全程数组 A(low:high)按非降次序分类。 LINK中值表示按分类次序给出
A下标的表，并把 p置于该表的开始处 //
global A(low:high),LINK(low,high)
if high-low+1<16 //当集合中的元素个数足够少 (<16)时，采用更有效的小规模集合上的分类算法直接分类 //
then call INSERTSORT1(A,LINK,low,high,p) //算法 2.7的改型 //
else mid←
call MERGESORT1(low,mid,q) //返回 q表 //
call MERGESORT1(mid+1,high,r) //返回 r表 //
call MERGE1(q,r,p) //将表 q和表 r归并成表 p//
endif
end MERGESORT1
h ig h ) / 2( lo w?
2009-7-27
算法 2.11 使用链接表归并已分类的集合
procedure MERGE1(q,r,p)
//q和 r是全程数组 LINK(1:n)中两个表的指针。归并这两个表，得到一个由 p所指示的新表。此表将
A中的元素按非降次序分类。 LINK(0)被定义 //
global n,A(1:n),LINK(1:n)
local integer i,j,k
i←q;j←r;k←0 //新表在 LINK(0)处开始 //
while i≠0 and j≠0 do //当两表均非空时 //
if A(i) ≤ A(j) //找较小的关键字 //
then LINK(k) ←i;k←i;i←LINK(i) //加一个新关键字到表中 //
else LINK(k) ←j;k←j;j←LINK(j) //加一个新关键字到表中 //
endif
repeat
if i=9 then LINK(k) = j
else LINK(k) = i
endif
end MERGE1
2009-7-27
MERGESORT1 的调用
在初次调用时，待分类的 n个元素放于 A(1:n)中。
LINK(1:n)初始化为 0；
初次调用,call MERGESORT1(1,n,p)
p作为按分类次序给出 A中元素的指示表的指针。
3）改进归并分类算法示例设元素表：（ 50,10,25,30,15,70,35,55）
采用 MERGESORT1对上述元素表分类（不做小规模集合的单独处理）
下表给出在每一次调用 MERGESORT1结束后,LINK数组的变化情况。
2009-7-27
在上表的最后一行,p=2返回，得到链表（ 2,5,3,4,7,1,8,6）
即,A(2)≤ A(5)≤ A(3)≤ A(4)≤ A(7)≤ A(1)≤ A(8)≤ A(6)
i ji j
k k k
j
k
2009-7-27
5,以比较为基础分类的时间下界任何以关键字比较为基础的分类算法，其最坏情况下的时间下界都为,Ω(nlogn)
利用 二元比较树 证明。
假设参加分类的 n个关键字 A(1),A(2),?,A(n) 互异。任意两个关键字的比较必导致 A(i)<A(j)或 A(i)>A(j)的结果。
以二元比较树描述元素间的比较过程：
若 A(i)<A(j)，进入下一级的 左分支
若 A(i)>A(j)，进入下一级的 右分支
2009-7-27
算法在 外部结点 终止。
从根到某外结点的 路径 代表某个特定输入情况下一种唯一的 分类排序序列 。
路径长度 表示生成该序列代表的分类表所需要的 比较次数。 而 最长的路径 代表算法在最坏情况下的执行情况，该路径的长度即是算法在最坏情况下所作的比较次数。
故，以比较为基础的分类算法的 最坏情况下界 等于该算法对应的比较树的 最小高度 。
2009-7-27
① 由于 n个关键字有 n!种可能的排列，所以二元比较树中将有 n!个外部结点,每种排列对应于某种特定输入情况下的分类情况，每个外部结点表示一种可能的分类序列。
② 设一棵二元比较树的所有 内结点 的级数均小于或等于 k，则该树中最多有 2k个外结点。 (引理 1.1)
记算法在最坏情况下所作的比较次数为 T(n),则有 T(n)=k,生成外结点所代表的分类序列所需的比较次数等于该外结点所在的级数 -1；
根据①和②的分析，有：
n!≤2 T(n)
化简：
当 n>1时，有 n!≥n(n -1)(n-2)?( )≥(n/2) n/2
当 n≥4 时，有 T(n)≥(n/2)log(n/2)≥(n/4)logn
故，任何以比较为基础的分类算法的最坏情况的时间下界为：
Ω(nlogn)
n/2
2009-7-27
2.5 快速分类任何一个基于比较来确定两个元素相对位置的排序算法需要 Ω(nlogn) 计算时间。如果我们能设计一个需要 O(n1ogn)时间的排序算法，则在渐近的意义上，这个排序算法就是最优的。许多排序算法都是追求这个目标。
下面介绍快速排序算法，它在平均情况下需要 O(nlogn)时间。这个算法是由 C.A.R.Hoare发明的。
1,问题描述分类问题
2.划分
快速分类是一种基于 划分 的分类方法；
划分,选取待分类集合 A中的某个元素 t，按照与 t的大小关系重新整理 A中元素，使得整理后的序列中所有在 t以前出现的元素均 小于等于 t，而所有出现在 t以后的元素均 大于等于 t。这一元素的整理过程称为 划分 （ Partitioning）。元素 t称为 划分元素 。
快速分类,通过反复地对待排序集合 进行划分 达到分类目的的分类算法。
2009-7-27
划分过程（ PARTITION）的算法描述算法 2.2 用 A(m)划分集合 A(m:p-1)
procedure PARTITION(m,p)
integer m,p,i; global A(m:p-1)
v←A(m);i←m //A(m) 是划分元素 //
loop
loop i←i+1 until A(i)≥v repeat // i 由左向右移 //
loop p←p -1 until A(p)≤v repeat //p由右向左移 //
if i<p then
call INTERCHANGE(A(i),A(p))
else exit
endif
repeat
A(m)←A(p) ； A(p)←v // 划分元素在位置 p//
end PARTITION
2009-7-27
注：
算法对集合 A(m:p-1)进行划分。并使用待划分区间的第一个元素 A(m)作为划分元素
A(p)不在划分区间内，但被定义，且 A(p） ≥ A(m)，用于限界
2009-7-27
例 2.5 划分实例
(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) i p
A,65 70 75 80 85 60 55 50 45 +∞ 2 9
|……………………………………|
A,65 45 75 80 85 60 55 50 70 +∞ 3 8
|…………………………|
A,65 45 50 80 85 60 55 75 70 +∞ 4 7
|………………|
A,65 45 50 55 85 60 80 75 70 +∞ 5 6
|……|
A,65 45 50 55 60 85 80 75 70 +∞ 6 5
|……………………|
A,60 45 50 55 65 85 80 75 70 +∞
划分元素定位于此交换划分元素
2009-7-27
经过一次,划分” 后，实现了对集合元素的调整：其中一个子集合的所有元素 均小于 等于另外一个子集合的所有元素。
按同样的策略对两个子集合进行分类处理。当子集合分类完毕后，整个集合的分类也完成了。这一过程避免了子集合的归并操作。这一分类过程称为快速分类 。
2009-7-27
3.快速分类通过反复使用划分过程 PARTITION实现对集合元素分类的算法。
算法 2.13 快速分类
procedure QUICKSORT(p,q)
//将数组 A(1:n)中的元素 A(p),…A(q) 按递增的方式分类。
A(n+1)有定义，且假定 A(n+1)←+ ∞//
integer p,q;global n,A(1:n)
if p<q then
j←q+1 //进入时,A(j)定义了划分区间 [p,q]的 上界,初次调用时 j=n+1
call PARTITION(p,j) //出口时,j待出此次划分后划分元素所在的 坐标位置 //
call QUICKSORT(p,j-1) //前一子集合上递归调用
call QUICKSORT(j+1,q) //后一子集合上递归调用
endif
end QUICKSORT
2009-7-27
4,快速分类分析
统计的对象：元素的 比较次数,记为,C(n)
两点假设
① 参加分类的 n个元素各不相同
② PARTITION中的划分元素 v是 随机 选取的（针对平均情况的分析）
随机选取划分元素,
在划分区间 [m,p]随机生成某一坐标,i←RANDOM(m.p -1)；
调换 A(m)与 A(i):v←A(i);A(i) ←A(m);i←m
作用：将随机指定的划分元素的值依旧调换到 A(m)位置。
之后，算法主体不变，仍从 A(m)开始执行划分操作。
2009-7-27
递归层次
QuickSort(1,n)
QuickSort(1,j1-1) QuickSort(j1-1,n)
QuickSort(1,j21-1) QuickSort(j21+1,j1-1) QuickSort(j1-1,j22-1) QuickSort(j22+1,n)
n个元素参加划分和分类去掉 1个第一级的划分元素
n-1个元素参加划分和分类去掉 2个第二级的划分元素
n-3个元素参加划分和分类去掉 4个第三级的划分元素第一层第二层第三层设在任一级递归调用上，调用 PARTITION处理的所有元素总数为 r，则，初始时 r=n，以后的每级递归上，由于删去了上一级的划分元素，故 r比上一级至少 1：
理想情况,第一级少 1，第二级少 2，第三级少 4,… ；
最坏情况,每次仅减少 1（如集合元素已经按照递增或递减顺序排列）
2009-7-27
最坏情况分析
记 最坏情况 下的元素比较次数是 Cw(n)；
PARTITION一次调用中的元素比较数是 p-m+1,故每级递归调用上，元素的比较次数等于该级所处理的待分类元素数。
最坏情况下，每级递归调用的元素总数仅比上一级少 1，
故 Cw(n)是 r由 n到 2的累加和。
即,Cw(n)= = Ο(n2)?
nr
r
2
2009-7-27
平均情况分析平均情况 是指集合中的元素以任一一种顺序排列，且任选所有可能的元素作为划分元素进行划分和分类，在这些所有可能的情况下，算法执行性能的 平均值 。
设调用 PARTITION(m,p)时，所选取划分元素 v恰好是
A(m:p-1)中的第 i小元素（ 1≤i≤p -m）的概率相等。则经过一次划分，所留下的待分类的两个子文件恰好是 A(m:j-1)和
A(j+1:p-1)的概率是,1/(p-m),m≤j<p 。则有，
其中，
n+1是 PARTITION第一次调用时所需的元素比较次数。
CA(0) = CA(1) = 0
nk AAnA knCkCnnC 11 ))()1((1)(
2009-7-27
化简上式可得：
CA(n)/(n+1) = CA(n-2)/(n-1)+2/n+2/(n+1)
= CA(n-3)/(n-2)+2(n-1)+2/n+2/(n+1)
= CA(1)/2+
由于所以得,CA(n)<2(n+1)loge(n+1) = Ο(nlogn)
13
/12
nk
k
)1(l o g/1 12
13
nk en xdx
nk
2009-7-27
5,快速分类算法的迭代模型
消去递归（略）
6,快速分类与归并分类比较两者平均情况时间都是 Ο(nlogn），平均情况下哪种快一些？
实验证明快速分类要快一些
2009-7-27
2.6 选择问题
1,问题描述给出含有 n个元素表 A(1:n)，要求确定其中的第 k小元素。
2,设计思路利用 PARTITION过程。如果划分元素 v测定在 A(j)的位置上，则有 j-1个元素小于或等于 A(j)，且有 n-j个元素大于或等于 A(j)。此时，
若 k=j，则 A(j)即是第 k小元素；否则，
若 k<j，则第 k小元素将出现在 A(1:j-1)中；
若 k>j，则第 k小元素将出现在 A(j+1:n)中。
2009-7-27
3,利用 PARTITION实现的选择算法
算法描述算法 2.15 找第 k小元素
procedure SELECT(A,n,k) //在数组 A(1:n)中找第 k小元素，并将之放在 A(k)中。 //
integer n,k,m,r,j;
m←1;r ← n+1;A(n+1) ←+∞ //A(n+1)被定义，并置为一大值，用于限界 //
loop //在进入循环时,1≤m≤k≤r≤n+1 //
j ←r //将剩余元素的最大下标加 1后置给 j //
call PARTITION(m.j) //返回 j,它使得 A(j)是第 j小的值 //
case
:k=j,return
:k<j,r←j //j是新的上界 //
:else,m←j+1 //k>j,j+1是新的下界 //
endcase
repeat
end SELECT
2009-7-27
算法分析两点假设
① A中的元素 互异
② 随机选取 划分元素，且选择 A中任一元素作为划分元素的 概率相同分析
每次调用 PARTITION（ m,j),所需的元素比较次数是
Ο(j-m+1)。
在执行一次 PARTITION后，或者找到第 k小元素，或者将在缩小的子集 (A(m,k-1)或 A(k+1,j))中继续查找。缩小的子集的元素数将 至少 比上一次划分的元素数 少 1。
2009-7-27
1) 最坏情况
SELECT的最坏情况时间是 Ο(n2)
当 A中的元素已经按照 递增 的顺序排列,且 k=n。
此时，需要 n次 调用 PARTITION过程，且每次返回的元素位置是子集中的第一个元素，子集合的元素数一次 仅减少１,而 j值不变。
则,n次调用的时间总量是
)())1(( 2
1
ni
n
2009-7-27
2) 平均情况设 是找 A(1:n)中第 k小元素的平均时间。 是
SELECT的平均计算时间，则有并定义则有,T(n)≤R(n)。
nk
k
AnA nTnT
1
1 )()(
)(nTA
k
k
A nTnR )}(m a x {)(?
)(nTkA
2009-7-27
定理 2.4 SELECT的平均计算时间 TA(n)是 Ο(n)
证明：
PARTITION和 SELECT中,case语句的执行时间是 Ο(n)。
在随机等概率选择划分元素时，首次调用 PARTITION中划分元素 v刚好是 A中第 i小元素的概率为 1/n,1≤ i≤ n。
则，存在正常数 c,c>0,有，
n≥2
且有，
n≥2
1 ) )(iTi)(nT(cn( n )T
nik
k
A
ki1
ik
An1
k
A
1 ) }(iRi)(nR{m axcnR ( n )
nikki1kn
1
( i ) }R( i )R{m axcn
1n
k
1n
1knk
n
1
2009-7-27
令 c≥R(1) 。利用 数学归纳法 证明，对所有 n≥2,有 R(n)≤4cn.
① 当 n=2时，由上式得：
② 假设对所有得 n,2≤n<m,有 R(n)≤4cn
③ 当 n = m时，有，
由于 R(n)是 n的非降函数，故在当 m为偶数而 k=m/2，或当 m为奇数而 k=(m+1)/2时,取得极大值。因此，
若 m为偶数,则若 m为奇数,则由于 TA(n)≤R(n),所以 TA(n)≤4cn 。 故,TA(n)=Ο(n)
R ( 1 ) }m a x { R ( 1 ),212cR ( n )
4 c n2,5 c
( i ) }R( i )R{m axcm)( 1m
k
1m
1kmkm
1
nR
1m
m / 2
m2 R ( i)cmR ( m )?
1m
m / 2
m
8c 4 cmicm
1m
1 ) / 2(m
m
2 R ( i )cmR ( m )?
1m
1 ) / 2(m
m
8c 4 cmicm
( i)R( i)R 1n
k
1n
1kn
2009-7-27
4,最坏情况是 Ο(n)的选择算法
1）采用两次取中间值的规则精心选取划分元素首先，将参加划分的 n个元素分成 组，每组有 r个元素 (r≥1) 。（多余的 个元素忽略不计）
然后，对这 组每组的 r个元素进行分类并找出其中间元素 mi,1≤i≤,共得 个中间值。
之后，对这 个中间值分类，并找出其中间值 mm。
将 mm作为划分元素执行划分。
2）算法描述
n/r
n/rrn?
n/r
n/rn/r
n/r
2009-7-27
算法 2.16 使用 二次取中规则 得选择算法的说明性描述
//在集合 A中找第 k小元素，使用两次取中规则 //
① 若 n≤r，则采用 插入法 直接对 A分类并返回第 k小元素
② 把 A分成大小为 r的 个子集合，忽略多余的元素
③ 设 M={m1,m2,…m } 是 子集合的 中间值集合
④ v←SELECT2(M,,)
⑤ j← PARTITION(A,v) //v作为划分元素，划分后 j等于划分元素所在位置的下标 //
⑥ case
:k=j,return(v)
:k<j,设 S是 A(1:j-1)中元素的集合
return(SELECT2(S,k,j-1))
:else,设 R是 A(j+1:n)中元素的集合
return(SELECT2(R,k-j,n-j))
endcase
end SELECT2
n/r
n/r
n/r2/n/r
2009-7-27
例：设 n=35,r=7。
分为 n/r = 5个元素组,B1,B2，
B3,B4,B5；每组有 7个元素。
B1-B5按照各组的 mi的非增次序排列。
mm = mi的中间值,1≤i≤5
由图所示有,
mm
中间值小于等于 mm的元素大于等于 mm的元素非降次序
B1 B2 B3 B4 B5
按照 mi的非降次序排列
2009-7-27
由于 r个元素的 中间值 是第 小元素。则，
至少有 个 mi小于或等于 mm；
至少有 个 mi大于或等于 mm。
则，至少有 个元素小于或等于（或大于或等于） mm。
当 r=5，则使用两次取中间值规则来选择 v=mm，可推出，
至少有 个元素小于或等于选择元素 v。
至多有 个元素大于 v。
至多有 0.7n+1.2个元素小于 v。
故，这样的 v可 近似平均 地划分 A中的 n个元素。
/2n / r1/2n / rn / r
2/n/r
2/r
/2n /rr/2
n/55.1
1,20,7 nn / 51,5n
2009-7-27
2) 算法分析记 T(n)是 SELECT2所需的最坏情况时间对特定的 r分析 SELECT2:选取 r=5。
假定 A中的元素各不相同，则有
① 若 n≤r，则采用插入法直接对 A分类并返回第 k小元素 → Ο(1)
② 把 A分成大小为 r的 个子集合，忽略多余的元素 → Ο(n)
③ 设 M={m1,m2,…m } 是 子集合的中间值集合 → Ο(n)
④ v←SELECT2(M,,) → T(n/5)
⑤ j← PARTITION(A,v) → Ο(n)
⑥ case →T(3n/4),n ≥24
:k=j,return(v)
:k<j,设 S是 A(1:j-1)中元素的集合 ; return(SELECT2(S,k,j-1))
:else,设 R是 A(j+1:n)中元素的集合 ; return(SELECT2(R,k-j,n-j))
endcase
end SELECT2
n/r
n/r
n/r2/n/r
2009-7-27
故有，
cn n ＜ 24,
T(n)＝
T(n/5)+T(3n/4)+cn n≥24
用归纳法可证：
T(n)≤20cn
即,T(n) = Ο(n)
2009-7-27
当 A中的元素 不尽相同步骤⑤经 PARTITION调用所产生的 S和 R两个子集合中可能存在一些元素 等于 当前的划分元素 v,可能导致 |S|或 |R|大于 0.7n+1.2。
此时上述处理 作一下改进：
方法一：将 A集合分成 3个子集合 U,S和 R，其中 U是有 A中所有与 v相同的元素组成,S是由 A中所有比 v小的元素组成,R则是 A中所有比 v大的元素组成。
同时步骤⑥更改：
case
:|S|≥k:return(SELECT2(S,k,|S|)
:|S|+|U|≥k:return(v)
:else,return(SELECT2(R,k-|S|-|U|,|R|))
endcase
从而保证 |S|+|R|≤0.7n+1.2 成立，故关于 T(n)的分析仍然成立。
T(n) = Ο(n)
2009-7-27
方法二：选取其他的 r值进行计算特例：当 r=5,且 A中的元素不尽相同。假设其中有 0.7n+1.2个元素比 v小而其余的元素都等于 v的情况。
则，经过 PARTITION，在这些等于 v的元素中至多有一半可能在 S中，故
|S|≤0.7n+1.2+(0.3n -1.2)/2=0.85n+0.6
同理,|R|≤0.85n+0.6
可得，步骤④和⑥此时所处理的元素总数将是
1.05n+0.6>n
不再是线性关系。故有 T(n)≠ Ο(n)
改进：
取 r=9。经计算可得，此时将有 个元素小于或等于 v，同时至少有同样多的元素大于或等于 v。
则当 n≥90 时,|S|和 |R|都至多为基于上述分析，有新的递推式：
n/92.5
72/6325.136/319/25.1)9/5.2(9/5.2 21 nnnnnnn
2009-7-27
故有，
c1n n＜ 90
T(n) ＝
T(n/9)+T(63n/72)+c1n n≥90
用归纳法可证：
T(n)≤72c1n
即,T(n) = Ο(n)
2009-7-27
SELECT2的实现
算法中需要解决的两个问题
如何确定子集合的中间值
当 r较小时，采用 INSERTIONSORT(A,i,j)直接对每组的 r个元素分类，在分类好的序列中，中间元素即为当前 r个元素的中间值。
如何保存 个子集合的中间值
注：各组找到的中间元素值将存放数组 A的前部
n/r
2009-7-27
算法 2.17SELECT2的 SPARKS的描述
procedure SEL(A,m,p,k)
//返回一个 i，使得 i∈[m,p],且 A(i)是 A(m:p)中第 k小元素,r是一个全程变量，其取值为大于
1的整数
global r; integer n,i,j
if p-m+1≤r then call INSERTIONSORT(A,m,p); return (m+k -1); endif
loop
n←p -m+1 //元素数 //
for i←1 to do // 计算中间值 //
call INSERTIONSORT(A,m+(i-1)*r,m+i*r-1) //将中间值收集到 A(m:p)的前部 //
call INTERCHANGE(A(m+i-1),A(m+(i-1)r + -1))
repeat
j←SEL(A,m,m+ -1,)//mm//
call INTERCHANGE(A(m),A(j)) //产生划分元素 //
j←p+1
call PARTITION(m,j)
case
:j-m+1=k,return(j)
:j-m+1>k,p←j -1
:else,k←k -(j-m+1);m←j+1
endcase
repeat
end SEL
n/r
n/r/2n/r
r/2
2009-7-27
2.7斯特拉森矩阵乘法矩阵乘法是线性代数中最常见的运算之一，它在数值计算中有广泛的应用。若 A和 B是 2个 n× n的矩阵，则它们的乘积 C=AB同样是一个 n× n的矩阵。 A和 B的乘积矩阵 C中的元素 C[i,j]定义为,
若依此定义来计算 A和 B的乘积矩阵 C，则每计算 C的一个元素 C[i,j]，需要做 n个乘法和 n-1次加法。因此，求出矩阵 C的 n2个元素所需的计算时间为
0(n3)。
2009-7-27
60年代末,Strassen采用了分治技术，将计算 2个 n阶矩阵乘积所需的计算时间改进到
O(nlog7)=O(n2.81)。
首先，我们还是需要假设 n是 2的幂。将矩阵
A,B和 C中每一矩阵都分块成为 4个大小相等的子矩阵，每个子矩阵都是 n/2× n/2的方阵。由此可将方程 C=AB重写为,
2009-7-27
由此可得,
C11=A11B11+A12B21
C12=A11B12+A12B22
C21=A21B11+A22B21
C22=A21B12+A22B22
如果 n=2，则 2个 2阶方阵的乘积可以直接用上式计算出来，共需 8次乘法和 4次加法。当子矩阵的阶大于 2时，为求 2个子矩阵的积，可以继续将子矩阵分块，直到子矩阵的阶降为 2。这样，就产生了一个分治降阶的递归算法
2009-7-27
分治法的计算时间耗费 T(n)应该满足：
这个递归方程的解仍然是 T(n)=O(n3)。因此，
该方法并不比用原始定义直接计算更有效。
究其原因，乃是由于没有减少矩阵的乘法次数。而矩阵乘法耗费的时间要比矩阵加减法耗费的时间多得多。要想改进矩阵乘法的计算时间复杂性，必须减少子矩阵乘法运算的次数。
2009-7-27
Strassen提出了一种新的算法来计算 2个 2阶方阵的乘积。他的算法只用了 7
次乘法运算，但增加了加、减法的运算次数
P=(A11+A22)(B11+B22)
Q=(A21+A22)B11 R=A11(B12-B22)
S=A22(B21-B11) T=(A11+A12)B22
U=(A21-A11)(B11+B12)
V=(A12-A22)(B21+B22)
用八个加减法计算 Cij
C11=P+S-T+V C12=R+T
C21＝ Q+S C22=P+R-Q+U
共用 7次乘法和 18次加减法按照解递归方程的套用公式法，其解为 T(n)=O(nlog7)≈O(n2.81)。
2009-7-27
有人曾列举了计算 2个 2阶矩阵乘法的 36种不同方法。但所有的方法都要做 7次乘法。除非能找到一种计算 2阶方阵乘积的算法，使乘法的计算次数少于 7次，按上述思路才有可能进一步改进矩阵乘积的计算时间的上界。但是 Hopcroft 和
Kerr(197l) 已经证明，计算 2个 2× 2矩阵的乘积,7次乘法是必要的。
因此，要想进一步改进矩阵乘法的时间复杂性，就不能再寄希望于计算 2× 2矩阵的乘法次数的减少。或许应当研究
3× 3或 5× 5矩阵的更好算法。在 Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.367)。而目前所知道的矩阵乘法的最好下界仍是它的平凡下界 Ω(n2)。
