2010-5-14 计算机算法设计与分析 1
第二章
递归与分治
2010-5-14 计算机算法设计与分析 2
递归的概念
? 简单地说，递归就是用自己来定义自己。
? 一般地说，一个递归过程 P可以表示为基语句
S(不含 P)和 P自身的组合 β：
P ?β(S,P)
? 这样的表示包含了过程不终止的可能，因此递
归算法应更准确地表述为
P ? if B then Q else β(S,P)
其中 Q也不包含 P,B为递归终止条件。
2010-5-14 计算机算法设计与分析 3
递归元
? 递归算法的思想是将对较大规模的对象的操作
归结为对较小规模的对象实施同样的操作。
? 这种规模的变化就体现在递归算法的变元中的
一类 (一个或几个 )变元上，这类变元被称之为
递归元。
? 递归元的变化是在递归定义中确定的，它的变
化应能导致递归算法的终止。
? 在递归算法的设计中递归元是非常重要的。
2010-5-14 计算机算法设计与分析 4
Hanoi塔问题
? 例 1,Hanoi塔问题：有 A,B,C三根柱子。 A
上有 n个圆盘，自下而上由大到小地叠在一起。
A B C
? 现要将 A上的全部圆
盘移到 B上，并要求,
(1)每次只能移动一个
圆盘； (2)任何时刻都
不允许将较大的圆盘
压在较小的圆盘上；
(3)圆盘只能在 A,B、
C三个柱子间移动。
? Hanoi塔的解可以很自然地看成这样一个过程：
(1)先将 A上面
n–1个盘移至 C。
(2)再将 A上剩下
的 1个盘移至 B。
(3)最后将 C上的
n–1个盘移至 B。
于是可得到如下的程序：
void Hanoi(int n,int Fr,int To,int As)
{
if (n > 0) {
Hanoi(n–1,Fro,Ass,To);
Move(Fro,To);
Hanoi(n–1,Ass,To,Fro)}
}
2010-5-14 计算机算法设计与分析 5
Hanoi塔问题的时间复杂性
? Hanoi塔问题的时间复杂性为 O(2n)。
? 证明：对 n归纳证明移动次数 move(n) = 2n– 1。
? 归纳基础：当 n = 1,move(1) = 1 = 21 – 1。
? 归纳假设：当 n ? k,move(n) = 2n – 1。
? 归纳步骤：当 n= k + 1,移动次数为
? move(k+1) = 2(move(k)) + 1 = 2(2k – 1) + 1
= 2k+1 – 1
? 由归纳法可知对任意的 n有 move(n) = 2n– 1
2010-5-14 计算机算法设计与分析 6
常见的递归形式
? 多变元递归；
? 多步递归；
? 嵌套递归；
? 联立递归
? 除基本的递归形式外，其它常见的递归
形式有四种，它们是：
2010-5-14 计算机算法设计与分析 7
多变元递归
? 多变元递归就是递归元多于一个的递归。? 例 2：整数划分问题：将一个正整数 n表示为
一系列正整数之和，
n = n1 + n2 +…+n k
其中 n1≥n2≥… ≥nk≥1,k≥1。
? 正整数 n的一个这种表示称为正整数 n的一个
划分。正整数 n的不同的划分的个数成为正整
数 n的划分数，记作 ρ(n)。
例如 ρ(6) = 11，即整数 6的划分数为 11种,
6,5+1,4+2,4+1+1,3+3,3+2+1,3+1+1+1
2+2+2,2+2+1+1,2+1+1+1+1,1+1+1+1+1+1
2010-5-14 计算机算法设计与分析 8
正整数的划分
? 在正整数的所有不同划分中，将最大加数 n1不
大于 m的划分个数记为 q(n,m),可以建立如下
的递归关系：
? 最简单情形, (1) q(n,1)=1,q(1,m) =1 n,m≥1;
? 递归关系, (2) q(n,n) = 1 + q(n,n–1),n＞ 1;
? 产生的新情况：
? (3) q(n,m) = q(n,m–1) + q(n–m,m),n＞ m＞ 1
? (4) q(n,m) = q(n,n),n＜ m。
1 n 或 m = 1
q(n,m) = 1 + q(n,n–1) n ≤ m
q(n,m–1)+q(n–m,m) n＞ m＞ 1
的二元递归函数：
q(n,m) {
if (n < 1) || (m < 1) return 0;
if (n == 1) || (m == 1) return 1;
if (n == 1) || (n < m) return 1 + q(n,n–1);
return q(n,m–1) + q(n–m,m); }
整数 n的划分数 ρ( = q(n,n)。
2010-5-14 计算机算法设计与分析 9
多步递归
? 若递归函数 f(x,y),其中 y是递归元，不仅与 f(x,
y–1)有关，而且与 f(x,y–2),……, 乃至 f(x,0)
有关，则称为多步递归。
? 例如 Fibonacci函数：
1 n = 0
F(n) = 1 n = 1
F(n–1) + F(n–2) n > 1
? Fibonacci函数是一个两步的递归函数。
2010-5-14 计算机算法设计与分析 10
嵌套递归
? 所谓嵌套递归是指递归调用中又含有递归调用，
又称为多重递归。
? 例如 Ackermann函数：
y + 1 x = 0
A(x,y) = A(x–1,1) y = 0
A(x–1,A(x,y–1)) x,y > 0
? Ackermann函数是一个双重的递归函数。同时
它也是个二元递归。
2010-5-14 计算机算法设计与分析 11
联立递归
? 联立递归是同时定义几个函数，它们彼此相互
调用，从而形成递归，又称间接递归。
? 例如 Hilbert图案，下面所示为 H1,H2和 H3：
H1 H2 H3
2010-5-14 计算机算法设计与分析 12
Hilbert图案
? 将 Hi记为 Ai,将 Hi旋转 90°,180°和 270°后的
图形分别记为 Bi,Ci和 Di，其中一、二级曲线
如下所示：
A1 B1 C1 D1
A2
D1A1
A1 B1
B2
C1
B1 B1
A1
C2
B1 C1
C1D1
D2
A1
D1D1
C1
2010-5-14 计算机算法设计与分析 13
Hilbert图案
? 于是可得出这些子曲线逐级间存在如下关系：
Ai+1,Di Ai Ai Bi
Bi+1,Ci Bi Bi Ai
Ci+1,Bi Ci Ci Di
Di+1,Ai Di Di Ci
其中，箭头表示曲线移动的方向，
? 于是 便可写出画这些曲线的递归子程序：
2010-5-14 计算机算法设计与分析 14
Hilbert图案
? 依据 有画 A的子程序：Ai+1,Di Ai Ai Bi
A(i) {
if (i > 0) { D(i – 1); x = x – h; ploting(x,y) ;
A(i – 1); y = y – h; ploting(x,y) ;
A(i – 1); x = x + h; ploting(x,y) ;
B(i – 1); }}
//*ploting(x,y)是从画笔现行坐标到坐标 (x,y)画条直线
? 类似地可以写出画 B,C和 D的曲线的子程序。
? 画 Hilbert曲线的程序在调用 A之前还应有一些
初始化的工作，如计算 h,移动画笔至起点。
2010-5-14 计算机算法设计与分析 15
画 Hilbert图案的时间复杂性
? Hilbert图案 Ai+1是由 Ai,Bi,Ci,和 Di中的四个图案,
再通过三根直线连接而成的。显然绘制 Ai,Bi,Ci,和
Di的复杂形式一样的。于是我们有如下的递推公式：
T(n) = 0 n = 04T(n–1) + 3 n＞ 0
? 不难推出,
T(n) = 4T(n–1) + 3 = 4(4T(n–2) + 3 ) + 3 = ??
n–1?
i=0= 4
n(4T(0) + 3) + 3 4i = 3 4i = 3(4n+1 – 1)
n?
i=0
不难推出, T(n) = 12*4n – 3。
所以，画 Hilbert图案的时间复杂性为 O(4n)。
2010-5-14 计算机算法设计与分析 16
Koch曲线
? Koch曲线是一种分形图形，其特点是它的每一
部分都是它自身。下面是 n=1和 n=2的 Koch曲线：
n = 1：
n = 2：
曲线 Ki+1由 4个 Koch曲线 Ki构成，并且每个
Ki的长度是 Ki+1长度的三分之一。
K0
K0 K0
K0
K1
K1 K1
K1
60°
–120° 构成方法是：画第一个 Ki；
旋转 60° ；
画第二个 Ki；
旋转 –120° ；
画第三个 Ki；
旋转 60° ；
画第四个 Ki。
2010-5-14 计算机算法设计与分析 17
绘制 Koch曲线的算法
? Koch(L,i) { //*L为长度,i为级数
? if (i == 0) Line(L) //*i为 0，画条长为 L的线段
? else {Koch(L/3,i – 1);
? Turn(60); Koch(L/3,i – 1);
? Turn(–120); Koch(L/3,i – 1);
? Turn(60); Koch(L/3,i – 1);}}
? Draw-Koch(L,θ,n) {//*将角度初始化为 θ；
? Turn(θ); Koch(L,n);}//*然后再画曲线 。
2010-5-14 计算机算法设计与分析 18
Koch曲线的三角形
? 右边是一个
由三条 Koch
曲线构成的
三角形：
2010-5-14 计算机算法设计与分析 19
绘制 Koch曲线的时间复杂度
? 设 T(n)是绘制 Koch曲线 Kn所需要的时间，
则从算法可知,T(n)满足如下递归方程：
T(n) = O(1) k = 04T(n–1) + O(1) k＞ 0
? 类似的，解此递归方程可得 T(n) = O(4n)。
2010-5-14 计算机算法设计与分析 20
递归方法小结
? 递归方法是将复杂问题分解为较为简单的子问
题的组合。这些子问题与原问题相似。
? 递归算法一定要有一个或几个最简单情况的计
算 (非递归分支 )，如果缺少将造成递归不终止。
? 递归算法是有层次的，低层的解组合成高层的
解。各层间最好通过参数传递来交流信息，如
使用全局量，则要注意全局量的及时修订。
2010-5-14 计算机算法设计与分析 21
分治法的基本思想
? 将一个规模为 n的问题分解为 k个规模较
小的子问题，这些子问题互相独立且与
原问题相同。递归地解这些问题，然后
将各个子问题的解合并在一起，从而得
到原问题的解。
? 分治法的一般的算法模式为：
? Divide-and-Conquer(P)
? {//|P|<=n0表示 P的规模不超过阈值 n0，可直接求解
? if (|P|<=n0) return Adhoc(P);
? divide P into smaller subinstants P1,..,Pk;
? for (i =1; i <= k; i++)
? yi = Divide-and-Conquer(Pi);
? return Merge(y1,…,y k);
? } //算法 Merge(y1,…,y k)表示将子问题的解合成 P的解
2010-5-14 计算机算法设计与分析 22
递归算法的时间复杂性
? 一般的，递归的时间复杂性可归结为递归方程：
1 n = 1T(n) ≤
aT(n~b) + D(n) n＞ 1
? 其中,a是子问题的个数,b是递减的步长,~
表示递减方式,D(n)是合成子问题的开销。
? 通常, 递归元的递减 方式 ~有两种：
1、减法，即 n – b,的形式
2,除法，即 n / b,的形式
2010-5-14 计算机算法设计与分析 23
递归算法的时间复杂性
? 若 ~为减法，即 n – b,则有,
T(n) = aT(n – b) + D(n)
= a(aT(n – 2b) + D(n – b)) + D(n) = ??
k–1?
i=0
= akT(1) + ai D(n – ib) = ak + ai D(n – ib)k–1?
i=0
? 这里 k = n / b。 不失一般性令 b = 1,则 k = n。
若设 D(n)为常数，则有 T(n) = O(an)。 即这种情
况下递归算法的时间复杂性为指数函数。
2010-5-14 计算机算法设计与分析 24
递归算法的时间复杂性
? 若 ~为除法，即 n / b,则有,
T(n) = aT(n / b) + D(n)
= a(aT(n / b2) + D(n / b)) + D(n) = ??
k–1?
i=0
= akT(1) + ai D(n / bi) = ak + ai D(n / bi)k–1?
i=0
? 这里 bk = n,所以 k = log b n。 于是：
ak = a = n = np,这里 p = log b a。logb n logb a
? 由此可知,T(n)的首项是 n的常数幂。
2010-5-14 计算机算法设计与分析 25
递归算法的时间复杂性
? 若递减方式为 n / b,则递归算法的时间复杂性
T(n) = np + ai D(n / bi)k–1?
i=0
这里 p = log b a。
? 这个递归方程的首项成为 np称为 ji齐次解，第
二项称为特解。特解一般很难估计。但是，对
于一些特殊的 D(n),可以给出其显式解。
? 一,D(n)为常数 c：
? 这时,ai D(n /bi)k–1?
i=0
c ai，k–1?
i=0
=
∵ ak = np
∴ 对 0 ? i < k有
ai = nj 且 j < p。
ai = nj 且 j < p。
? 这是低于 p次的多项式, 所以 T(n) = O(np)。
2010-5-14 计算机算法设计与分析 26
递归算法的时间复杂性
? 二,D(n)为线性函数 cn：
? 这时,ai D(n /bi)k–1?
i=0
ai(cn/bi)k–1?
i=0
= = cn (a/b) i
k–1?
i=0
(I)
? ⑴ 若 a = b,则 a / b = 1,从而 (I)式为 cnk
又 k = log b n,p = log b a = 1,因此有
T(n) = np + cnk = n + cnlog b n = O(nlog b n)
2010-5-14 计算机算法设计与分析 27
递归算法的时间复杂性
? 二,D(n)为线性函数 cn：
? 这时,ai D(n /bi)k–1?
i=0
ai(cn/bi)k–1?
i=0
= = cn (a/b) i
k–1?
i=0
(I)
? ⑴ 若 a = b,则 a / b = 1,从而 (I)式为 cnkT(n) = O(nlog b n)
? ⑵ 若 a ? b,则 (I)式为 cn((a/b)k – 1)/(a/b – 1)
又 (a/b)k = ak / bk = np / n ∵ bk = b log n = n log b= nb b
令 c / (a/b –1)为 c’,则 (I)式为 c’np –c’n, 从而
T(n) = c1np + c2n,这里 c1 = 1+ c’,c2 = –c’ 。
2010-5-14 计算机算法设计与分析 28
递归算法的时间复杂性
? 二,D(n)为线性函数 cn：
? 这时,ai D(n /bi)k–1?
i=0
ai(cn/bi)k–1?
i=0
= = cn (a/b) i
k–1?
i=0
(I)
? ⑴ 若 a = b,则 a / b = 1,从而 (I)式为 cnkT(n) = O(nlog b n)；
? ⑵ 若 a ? b,则 T(n) = O(np + n)；
显然：
若 a < b,p = log ba < 1,np < n，
反之,若 a > b,则 np > n。
?①若 a < b,则 T(n) = O(n)；
?②若 a > b,则 T(n) = O( p)。
2010-5-14 计算机算法设计与分析 29
递归算法的时间复杂性
? 总之，当 D(n)线性函数 cn时，递归算法
的时间复杂性为：
T(n) =
O(n) 当 a < b时
O(nlogbn) 当 a = b时
O(np) 当 a > b时
其中,p = log ba。
2010-5-14 计算机算法设计与分析 30
递归算法的时间复杂性
? 二,D(n)为 n的高次幂，即 D(n) = nx：
? T(n) = ai D(n /bi)k–1?
i=0
ak + ai(n/bi)xk–1?
i=0
= ak +
∵ n = bk ∴ (n/bi)x = (bk–i)x = (bx)k–i = D(b)k/ D(b)i= D(b k (a/D(b))ik–1?
i=0
ak +
? ⑴ 若 a = D(b),则
∵ a / D(b) = 1
∴ T(n) = ak + akk = np(1 + log bn) = O(nplog bn)
T(n) = O(nplog bn)
2010-5-14 计算机算法设计与分析 31
递归算法的时间复杂性
? 二,D(n)为 n的高次幂，即 D(n) = nx：
? T(n) = ai D(n /bi)k–1?
i=0
ak + ai(n/bi)xk–1?
i=0
= ak +
= D(b)k (a/D(b))ik–1?
i=0
ak +
? ⑴ 若 a = D(b),则 T(n) = O(nplog bn)
? ⑵ 若 a ? D(b),则
T(n) = ak + D(b)k(ak/ D(b)k – 1)/(a/ D(b) – 1)
= c1ak +c2D(b)k = c1nlog a + c2nlog D(b) b b
其中,c1 = 1 + 1/(a/D(b) – 1),c2 = 1/(1 – D(b))
T(n) = O(nlog a + nlog D(b) )b b
2010-5-14 计算机算法设计与分析 32
递归算法的时间复杂性
? 二,D(n)为 n的高次幂，即 D(n) = nx：
? T(n) = ai D(n /bi)k–1?
i=0
ak + ai(n/bi)xk–1?
i=0
= ak +
= D(b)k (a/D(b))ik–1?
i=0
ak +
? ⑴ 若 a = D(b),则 T(n) = O(nplog bn)
? ⑵ 若 a ? D(b),则 T(n) = O(nlog a + nlog D(b) )b b
∵ D(b) = bx,∴ log bD(b) = log bbx = x
若 a > D(b),则 log ba > log bD(b),即 p > x。
反之，则 p < x。
?于是
①若 a < D(b),则 T(n) = O(n)；
②若 a > D(b),则 T(n) = O(np)。
2010-5-14 计算机算法设计与分析 33
递归算法的时间复杂性
? 总之，当 D(n)幂函数 nx时，递归算法的时
间复杂性为：
T(n) =
O(nx) 当 a < D(b)时
O(nplogbn) 当 a = D(b)时
O(np) 当 a > D(b)时
其中,p = log ba。
2010-5-14 计算机算法设计与分析 34
求解递归方程
? 考虑下列递归方程,T(1) = 1
? ⑴ T(n) = 4T(n/2) +n
? ⑵ T(n) = 4T(n/2) +n2
? ⑶ T(n) = 4T(n/2) +n3
? 解：方程中均为 a = 4,b = 2,其齐次解为 n2。
? 对⑴,∵ a > b1 (D(n) = n) ∴ T(n) = O(n2)；
? 对⑵,∵ a = b2 (D(n) = n2)∴ T(n) = O(n2logn)；
? 对⑶,∵ a < b3 (D(n) = n3) ∴ T(n) = O(n3)；
2010-5-14 计算机算法设计与分析 35
求解递归方程
? 考虑递归方程, T(n) = 1 n = 12T(n/2) +nlog n n > 1
? 解,∵ a = b = 2∴ 齐次解为 n。
? 因 D(n) = nlogn,非幂函数，只好将 T(n)展开,
? T(n) = ai D(n /bi)k–1?
i=0
ak + 2i (n /2i)log(n /2i)k–1?
i=0
n +=
nlog(n /2i)k–1?
i=0
n += n(logn –log2i )k–1?
i=0
n += ilog2)
= n + knlog n – n(k – 1)k/2nk2/2 + nk/2 又 k = log n
= n + (nlog2n)/2 +(n logn)/2 = O(nlog2n)
2010-5-14 计算机算法设计与分析 36
二分搜索有序表的算法分析
? Binary-Search(L,n,z)
? {k = 1; m = n; //*k和 m分别为搜索部分的首和尾
? flag = 0; //*找到标志初始为 0
? while (k <= m && flag = 0) {
? j = ?(k + m) / 2? ; //*取中点下标
? if (z == L[j]) flag = 1 //* 找到了标志为 1
? else if (z < L[j]) m = j – 1 //*小于中点，尾前移
? else k = j + 1 //*大于中点，首后移
? }
2010-5-14 计算机算法设计与分析 37
二分搜索有序表的算法分析
[n]
[n/2] [n/2]
[n/4] [n/4] [n/4] [n/4]
?? ?? ??
[1] [1] [1] [1]??
?log n? + 1
? 二分搜索的每次循环查找区间减半，查找区间
构成一棵二叉树，最坏的情况是一直走到二叉
树的叶子。因此算法的复杂度为 log n + 1。
2010-5-14 计算机算法设计与分析 38
二分搜索有序表的算法分析
? 我们也可以证明二分搜索的算法复杂度
为 logn + 1。
W(n) = W(?n/2? ) + 1 n > 1 1 n = 1
? 显然，我们有：
? 于是我们可以对 n进行归纳证明有：
W(n) = ?log n? + 1
2010-5-14 计算机算法设计与分析 39
二分搜索有序表的算法分析
? 归纳证明 W(n) = ?log n? + 1。
? 证明：归纳基础：当 n = 1,有
W(n) = 1 = ?log 1? + 1= ?log n? + 1
? 归纳假设：对 1 ? k < n 有 W(k) = ?log k? + 1。
? 于是有：
? W(k) = W( ?n/2? ) + 1 (∵ ?n/2? < n )
? = ( ?log ?n/2?? + 1) + 1
当 n为偶数时,?n/2? = n/2；
当 n为奇数时,?n/2? = (n – 1) / 2。
所以，
log ?n/2? = log n – 1 若 n为偶数log (n – 1) – 1 若 n为奇数
? 所以,无论如何总有,W(n) = ?long n?+ 1二分搜索算法的时间复杂度为 O(log n)。
2010-5-14 计算机算法设计与分析 40
大整数的乘法
? 设 X和 Y都是 n位的二进制整数。如果用常规的
乘法计算乘积 XY,其时间复杂性为 O(n2)。
? 将 X和 Y都分成 2段，即
X = A2n/2 + B,Y = C2n/2 + D
? 于是, XY = (A2n/2 + B)(C2n/2 + D)
= AC2n +(AD+BC)2n/2 + BD
? 这样有, T(n) = 4T(n/2) + O(n)
因为 a = 4 > D(b) = 2,所以
= O(nlog4))2
无效果！
将 XY改写成：
XY = AC2n +(A–B)(D–C)+AC+BD)2n/2 + BD
? 这样有, T(n) = 3T(n/2) + (n)
同样因为 a = 4 > D(b) = 2,所以
( l 3 )1.59
2010-5-14 计算机算法设计与分析 41
Strassen矩阵乘法
? 矩阵乘法的时间复杂性为 O(n3)。
? 如果将矩阵分为 4个大小相等的子矩阵，则
C11 C12
C21 C22 =
A11 A12
A21 A22
B11 B12
B21 B22
? C11 = A11B11 + A12B21 C12 = A11B12 + A12B22
? C21 = A21B11 + A22B21 C11 = A21B12 + A22B22
? 这样有, T(n) = 8T(n/2) + O(n2)
因为 a = 8 > D(b) = 22 = 4,所以
= O(n log8)) 3
也无效果！
2010-5-14 计算机算法设计与分析 42
Strassen矩阵乘法
? 若改为,
M1 = A11(B12 – B22) M2 = (A11 + A12)B22
M3 = (A21 + A22)B11 M4 = A22(B21 – B11)
M5 = (A11 + A22) (B11 + B22)
M6 = (A12 – A22) (B21 + B22)
M7 = (A11 – A21) (B11 + B12)
C11 = M5+M4–M2+M6 C12 = M1 + M2
C21 = M3 + M4 C11 = M5+M1–M3 –M7
? 这样有, T(n) = 7T(n/2) + O(n2)≤ O(n log7 )2.82
? 目前的结果为, O(n2) ≤ O(n2.376)
2010-5-14 计算机算法设计与分析 43
棋盘覆盖问题
? 一个 2k× 2k的特殊棋盘是其中含有一个特殊方
格的棋盘，如左下图为 k=2的一个特殊棋盘。
? 现在任意给定一个 2k× 2k的特殊棋盘，要用右
下图所示的 L型骨牌来无重叠的覆盖它。
1
11
2
2 2
3 3
3
4
4 4
5
55
在 2k× 2k的棋
盘覆盖中要用
到 (4k–1)/3个 L
型骨牌。
2010-5-14 计算机算法设计与分析 44
棋盘覆盖问题的分析
? 当 k>0时，将 2k× 2k的棋盘分割成 4个 2k–1× 2k–1
的子棋盘，如右下图所示：
2k–1× 2k–1 2k–1× 2k–1
2k–1× 2k–1 2k–1× 2k–1
? 特殊方格必定位于 4个子棋盘之一中。
然而，这样一来四个子棋
盘的情形就不一致了。因
为递归求解是将问题归结
到较小的规模的同一问题，
所以就需要将三个正常子
棋盘也转化成特殊棋盘。
为此，可以用一个 L型骨
牌来覆盖其余三个子棋盘
的会合处，如左图所示。
这样原问题转化成了四个
较小规模的子问题。递归
地分割下去直至单格棋盘。
2010-5-14 计算机算法设计与分析 45
棋盘覆盖的算法
? 棋盘覆盖 (参数表 ) {
? 如果是单个格子，则返回；
? 将棋盘划分成尺寸为一半的子棋盘；
? 判断特殊方格在哪个子棋盘中，再用相应的
L型 骨牌覆盖相应结合部，即不含特殊方格的
部分在结合部的三个方格；并记下它们的位置，
作为个部分的特殊方格；
? 依次对左上角、右上角、左下角和右下角这
四个子棋盘进行棋盘覆盖； }
2010-5-14 计算机算法设计与分析 46
棋盘覆盖算法中的参数
参数表中应有哪些参数呢？? 递归元：棋盘尺寸 size=2k。 递归时棋盘尺寸减
半，即 size=size/2； 当 size为 1时递归终止。
? 表示棋盘位置参数，即棋盘左上角方格的列
行号 tr和 tc,每次用 size/2调整子棋盘位置。
? 表示特殊方格位置的参数，即特殊方格的行
号 dr和列号 dc。
? 棋盘用一个二维整型数组 Board表示。
? L型骨牌覆盖的顺序用全局变量 tile表示。
请同学们自己用设计程序实现此算法。
2010-5-14 计算机算法设计与分析 47
棋盘覆盖算法的正确性
? 要证明一个算法的正确性，需要证明两点：
? (1)算法的部分正确性；
? (2)算法的终止性。
? 下面我们用归纳法证明棋盘覆盖算法的部分正
确性：
归纳基础：对尺寸为 21的特殊棋盘，无论特殊
方格在什么位置，显然都可正确覆盖。
? 假设对尺寸 2k–1的特殊棋盘均可正确覆盖。
? 对尺寸 2k的特殊棋盘，算法划分为四个尺寸为
2k–1的子棋盘，再用一块 L型骨牌覆盖三个正常
子棋盘的结合处后，恰好形成四个尺寸 2k–1的
特殊棋盘，由归纳假设，它们均可正确覆盖。
因而也正确覆盖了尺寸 2k的特殊棋盘。
? 由归纳法可知，棋盘覆盖算法是部分正确。
算法的终止性：
递归的终止条件为递归元 size为 1时递归终止。
递归元 size的初值为 2k。 每次递归时递归元减
半，即 size=size/2； 因此，必然在有穷步内递
减为 1。
? 所以此算法必定终止。
? 由部分正确性和终止性可知，此算法是完全正
确的。
2010-5-14 计算机算法设计与分析 48
? 设 T(k)是棋盘覆盖算法覆盖 2k× 2k的棋盘所需
要的时间，则从算法的分治策略可知,T(k)满
足如下递归方程：
棋盘覆盖算法的复杂性
T(k) = O(1) k = 04T(k–1) + O(1) k＞ 0
? 递归元递减方式是减法 k – 1,a = 4,因此
T(k) = O(4k)。
? 由于覆盖 2k× 2k的棋盘要用 (4k–1)/3个 L型骨牌，
故此算法是一个在渐进意义下最优的算法。
2010-5-14 计算机算法设计与分析 49
最接近点对问题
? 给定平面上 n个点，在 n个点组成的所有点对中，
找出其中相互距离的最小一对点。
? 此问题的简单解法是，算出每个点与其它 n–1
个点之间的距离，再找出其中距离最小的一对
点。这样做的时间复杂性为 O(n2)。
? 下面用分治法构造一个时间复杂性为 O(nlogn)
的算法。
? 为此我们先考虑一维的情况：
2010-5-14 计算机算法设计与分析 50
一维最接近点对
? 设 S为 x轴上 n个点的集合，求 S中最接近点对。
? 假设用 x轴上某个点 m划分 S为 S1和 S2,使得
S1={x∈ S | x≤m},S2={x∈ S | x＞ m}。
m
S1 S2
? 递归地在 S1和 S2中找出其最接近点对 {p1,p2}
和 {q1,q2},并设 d = min{|p1,p2|,|q1,q2|}
p1 p2 q1 q2
? 易知,S中最接近点对是 {p1,p2}或 {q1,q2}，
或 {p3,q3},这里 p3=max{S1},q3 =min{S2}。
p3 q3
2010-5-14 计算机算法设计与分析 51
一维最接近点对算法
? bool Cpair1(S,d)
? {
? n = |S|;
? if (n < 2) { d = ∞; return false }
? m = S中各点的坐标的中位数；
? 构造 S1和 S2; // S1={x?S | x?m},S2={x?S | x>m}
? Cpair1(S1,d1);
? Cpair1(S2,d2); //分别求 S1和 S2的最接近点对
? p=max{S1}; q =min{S2}; d = mim{d1,d2,q – p};
? return true
? }
2010-5-14 计算机算法设计与分析 52
一维最接近点对算法复杂性
? 如果对 S的分割不平衡的话，最坏的情况是 S1
仅含一个点，这时算法的复杂性为 O(n2)。
? 所以要采用中位数 m来分割 S。
? 该算法的分割步骤和合并步骤总共耗时 O(n)，
因此算法耗时满足递归方程
T(n) = O(1) n＜ 02T(n/2) + O(n) n≥4
? 因为 a = 2 = D(b),可知 T(n) = O(nlogn)。
2010-5-14 计算机算法设计与分析 53
平面最接近点对
? 做一条直线 L,x=m,将 S分割为 S1和 S2,其中
m为所有点的 x坐标的中位数。递归地求得 S1
和 S2中的最小距离 d1和 d2，令 d=min{d1,d2}。
L
S1 S2d1 d2
? 但是 S1和 S2之间的最小距离却需要考察 S1和 S2
在 l两侧距离不超过 d的区域 P1和 P2间的点对。
d
P1
d
P2
? P1和 P2间的点对均为最近点对
的候选，最坏情况有 n2/4个。
? 而实际上，对 P1中的任意一点，
最多只需要考察 P2中的 6个点。
2010-5-14 计算机算法设计与分析 54
最多只需要考察 6个点
? 考虑 P1中的任意一点 p,它若与 P2中的点 q构成
最接近点对，则其距离必定小于 d。 这样的点
必定落在一个 d× 2d的矩形 R内：
d
d
P1 P2
p
R
L
? 在矩形 R中最多有 6个点。? 不然的话，可以将矩形 R分
成 6个 (d/2)× (2d/3)个小矩形，
? 每个小矩形对角线的长度为
5d/6。 (d/2)2+(2d/3)2=25d2/36
? 若 R中有 6个以上的点，则必
有两点 u,v在同一小矩形内，
于是 |uv|＜ 5d/6。 矛盾。
所以 R中至多有 6个点，即对
P1中的每个点至多只需要考
察 P2中的 6个点就可以了。
? 分别将 P1和 P2中的点按 y坐
标排序；再对 P1中的每个点
p,考察 P2中 y坐标在 y(p)± d
范围内的点 (最多 6个 )。
2010-5-14 计算机算法设计与分析 55
平面最接近点对的算法
? bool Cpair2(S,d)
? { n = |S|;
? if (n<2) { d = ∞; return false}
? m = S中各点 x坐标的中位数；构造 S1和 S2；
? Cpair2(S1,d1); Cpair2(S2,d2); dm=min(d1,d2)
? 构造 P1和 P2；
? //P1={p|m–dm?x(p)?m},P2={q|m<x(q)?m+dm}
? 将 P1和 P2中的点按 y坐标值排序；
? 依次扫描 P1中点 u并计算 u与 P2中 y坐标在 y(u)± dm
范围内的点 (最多 6个 )；设 dl是这样找到的最小距离；
? d = min(dm,dl);
? return true }
2010-5-14 计算机算法设计与分析 56
最接近点对的算法复杂性
? 在算法中：
? 计算中位数和 min需时为常数。
? 将 S分割为 S1和 S2需时为 O(n)。
? 在排序后的 P1和 P2中找最小距离 dl需时为 O(n)。
? 对 P1和 P2排序在最坏情况下需时 O(nlogn),这
不符合要求。
若在整个算法开始之前对各点的 y坐标进行一
次预排序，则在递归中就无须再排序，只要对
P1或 P2进行线性扫描即可，需时仍为 O(n)。
? 由此易知递归需时为 O(nlogn),预排序需时为
O(nlogn),因而整个算法需时为 O(nlogn)。
2010-5-14 计算机算法设计与分析 57
分治法总结
? 分治法的基本做法是：
? (1)将规模为 n的问题分解为 k个规模较小的子问
题。这些子问题相互独立且与原问题相同。
? (2)递归地解这些子问题。
? (3)然后将子问题合并得到原问题的解。
? 分治法的时间复杂性：
? 子问题的复杂性当然低于原问题。但是整体上
能否降低复杂性还取决于合并。通过降低合并
的复杂性可以降低原问题求解的复杂性。
第二章
递归与分治
2010-5-14 计算机算法设计与分析 2
递归的概念
? 简单地说，递归就是用自己来定义自己。
? 一般地说，一个递归过程 P可以表示为基语句
S(不含 P)和 P自身的组合 β：
P ?β(S,P)
? 这样的表示包含了过程不终止的可能，因此递
归算法应更准确地表述为
P ? if B then Q else β(S,P)
其中 Q也不包含 P,B为递归终止条件。
2010-5-14 计算机算法设计与分析 3
递归元
? 递归算法的思想是将对较大规模的对象的操作
归结为对较小规模的对象实施同样的操作。
? 这种规模的变化就体现在递归算法的变元中的
一类 (一个或几个 )变元上，这类变元被称之为
递归元。
? 递归元的变化是在递归定义中确定的，它的变
化应能导致递归算法的终止。
? 在递归算法的设计中递归元是非常重要的。
2010-5-14 计算机算法设计与分析 4
Hanoi塔问题
? 例 1,Hanoi塔问题：有 A,B,C三根柱子。 A
上有 n个圆盘，自下而上由大到小地叠在一起。
A B C
? 现要将 A上的全部圆
盘移到 B上，并要求,
(1)每次只能移动一个
圆盘； (2)任何时刻都
不允许将较大的圆盘
压在较小的圆盘上；
(3)圆盘只能在 A,B、
C三个柱子间移动。
? Hanoi塔的解可以很自然地看成这样一个过程：
(1)先将 A上面
n–1个盘移至 C。
(2)再将 A上剩下
的 1个盘移至 B。
(3)最后将 C上的
n–1个盘移至 B。
于是可得到如下的程序：
void Hanoi(int n,int Fr,int To,int As)
{
if (n > 0) {
Hanoi(n–1,Fro,Ass,To);
Move(Fro,To);
Hanoi(n–1,Ass,To,Fro)}
}
2010-5-14 计算机算法设计与分析 5
Hanoi塔问题的时间复杂性
? Hanoi塔问题的时间复杂性为 O(2n)。
? 证明：对 n归纳证明移动次数 move(n) = 2n– 1。
? 归纳基础：当 n = 1,move(1) = 1 = 21 – 1。
? 归纳假设：当 n ? k,move(n) = 2n – 1。
? 归纳步骤：当 n= k + 1,移动次数为
? move(k+1) = 2(move(k)) + 1 = 2(2k – 1) + 1
= 2k+1 – 1
? 由归纳法可知对任意的 n有 move(n) = 2n– 1
2010-5-14 计算机算法设计与分析 6
常见的递归形式
? 多变元递归；
? 多步递归；
? 嵌套递归；
? 联立递归
? 除基本的递归形式外，其它常见的递归
形式有四种，它们是：
2010-5-14 计算机算法设计与分析 7
多变元递归
? 多变元递归就是递归元多于一个的递归。? 例 2：整数划分问题：将一个正整数 n表示为
一系列正整数之和，
n = n1 + n2 +…+n k
其中 n1≥n2≥… ≥nk≥1,k≥1。
? 正整数 n的一个这种表示称为正整数 n的一个
划分。正整数 n的不同的划分的个数成为正整
数 n的划分数，记作 ρ(n)。
例如 ρ(6) = 11，即整数 6的划分数为 11种,
6,5+1,4+2,4+1+1,3+3,3+2+1,3+1+1+1
2+2+2,2+2+1+1,2+1+1+1+1,1+1+1+1+1+1
2010-5-14 计算机算法设计与分析 8
正整数的划分
? 在正整数的所有不同划分中，将最大加数 n1不
大于 m的划分个数记为 q(n,m),可以建立如下
的递归关系：
? 最简单情形, (1) q(n,1)=1,q(1,m) =1 n,m≥1;
? 递归关系, (2) q(n,n) = 1 + q(n,n–1),n＞ 1;
? 产生的新情况：
? (3) q(n,m) = q(n,m–1) + q(n–m,m),n＞ m＞ 1
? (4) q(n,m) = q(n,n),n＜ m。
1 n 或 m = 1
q(n,m) = 1 + q(n,n–1) n ≤ m
q(n,m–1)+q(n–m,m) n＞ m＞ 1
的二元递归函数：
q(n,m) {
if (n < 1) || (m < 1) return 0;
if (n == 1) || (m == 1) return 1;
if (n == 1) || (n < m) return 1 + q(n,n–1);
return q(n,m–1) + q(n–m,m); }
整数 n的划分数 ρ( = q(n,n)。
2010-5-14 计算机算法设计与分析 9
多步递归
? 若递归函数 f(x,y),其中 y是递归元，不仅与 f(x,
y–1)有关，而且与 f(x,y–2),……, 乃至 f(x,0)
有关，则称为多步递归。
? 例如 Fibonacci函数：
1 n = 0
F(n) = 1 n = 1
F(n–1) + F(n–2) n > 1
? Fibonacci函数是一个两步的递归函数。
2010-5-14 计算机算法设计与分析 10
嵌套递归
? 所谓嵌套递归是指递归调用中又含有递归调用，
又称为多重递归。
? 例如 Ackermann函数：
y + 1 x = 0
A(x,y) = A(x–1,1) y = 0
A(x–1,A(x,y–1)) x,y > 0
? Ackermann函数是一个双重的递归函数。同时
它也是个二元递归。
2010-5-14 计算机算法设计与分析 11
联立递归
? 联立递归是同时定义几个函数，它们彼此相互
调用，从而形成递归，又称间接递归。
? 例如 Hilbert图案，下面所示为 H1,H2和 H3：
H1 H2 H3
2010-5-14 计算机算法设计与分析 12
Hilbert图案
? 将 Hi记为 Ai,将 Hi旋转 90°,180°和 270°后的
图形分别记为 Bi,Ci和 Di，其中一、二级曲线
如下所示：
A1 B1 C1 D1
A2
D1A1
A1 B1
B2
C1
B1 B1
A1
C2
B1 C1
C1D1
D2
A1
D1D1
C1
2010-5-14 计算机算法设计与分析 13
Hilbert图案
? 于是可得出这些子曲线逐级间存在如下关系：
Ai+1,Di Ai Ai Bi
Bi+1,Ci Bi Bi Ai
Ci+1,Bi Ci Ci Di
Di+1,Ai Di Di Ci
其中，箭头表示曲线移动的方向，
? 于是 便可写出画这些曲线的递归子程序：
2010-5-14 计算机算法设计与分析 14
Hilbert图案
? 依据 有画 A的子程序：Ai+1,Di Ai Ai Bi
A(i) {
if (i > 0) { D(i – 1); x = x – h; ploting(x,y) ;
A(i – 1); y = y – h; ploting(x,y) ;
A(i – 1); x = x + h; ploting(x,y) ;
B(i – 1); }}
//*ploting(x,y)是从画笔现行坐标到坐标 (x,y)画条直线
? 类似地可以写出画 B,C和 D的曲线的子程序。
? 画 Hilbert曲线的程序在调用 A之前还应有一些
初始化的工作，如计算 h,移动画笔至起点。
2010-5-14 计算机算法设计与分析 15
画 Hilbert图案的时间复杂性
? Hilbert图案 Ai+1是由 Ai,Bi,Ci,和 Di中的四个图案,
再通过三根直线连接而成的。显然绘制 Ai,Bi,Ci,和
Di的复杂形式一样的。于是我们有如下的递推公式：
T(n) = 0 n = 04T(n–1) + 3 n＞ 0
? 不难推出,
T(n) = 4T(n–1) + 3 = 4(4T(n–2) + 3 ) + 3 = ??
n–1?
i=0= 4
n(4T(0) + 3) + 3 4i = 3 4i = 3(4n+1 – 1)
n?
i=0
不难推出, T(n) = 12*4n – 3。
所以，画 Hilbert图案的时间复杂性为 O(4n)。
2010-5-14 计算机算法设计与分析 16
Koch曲线
? Koch曲线是一种分形图形，其特点是它的每一
部分都是它自身。下面是 n=1和 n=2的 Koch曲线：
n = 1：
n = 2：
曲线 Ki+1由 4个 Koch曲线 Ki构成，并且每个
Ki的长度是 Ki+1长度的三分之一。
K0
K0 K0
K0
K1
K1 K1
K1
60°
–120° 构成方法是：画第一个 Ki；
旋转 60° ；
画第二个 Ki；
旋转 –120° ；
画第三个 Ki；
旋转 60° ；
画第四个 Ki。
2010-5-14 计算机算法设计与分析 17
绘制 Koch曲线的算法
? Koch(L,i) { //*L为长度,i为级数
? if (i == 0) Line(L) //*i为 0，画条长为 L的线段
? else {Koch(L/3,i – 1);
? Turn(60); Koch(L/3,i – 1);
? Turn(–120); Koch(L/3,i – 1);
? Turn(60); Koch(L/3,i – 1);}}
? Draw-Koch(L,θ,n) {//*将角度初始化为 θ；
? Turn(θ); Koch(L,n);}//*然后再画曲线 。
2010-5-14 计算机算法设计与分析 18
Koch曲线的三角形
? 右边是一个
由三条 Koch
曲线构成的
三角形：
2010-5-14 计算机算法设计与分析 19
绘制 Koch曲线的时间复杂度
? 设 T(n)是绘制 Koch曲线 Kn所需要的时间，
则从算法可知,T(n)满足如下递归方程：
T(n) = O(1) k = 04T(n–1) + O(1) k＞ 0
? 类似的，解此递归方程可得 T(n) = O(4n)。
2010-5-14 计算机算法设计与分析 20
递归方法小结
? 递归方法是将复杂问题分解为较为简单的子问
题的组合。这些子问题与原问题相似。
? 递归算法一定要有一个或几个最简单情况的计
算 (非递归分支 )，如果缺少将造成递归不终止。
? 递归算法是有层次的，低层的解组合成高层的
解。各层间最好通过参数传递来交流信息，如
使用全局量，则要注意全局量的及时修订。
2010-5-14 计算机算法设计与分析 21
分治法的基本思想
? 将一个规模为 n的问题分解为 k个规模较
小的子问题，这些子问题互相独立且与
原问题相同。递归地解这些问题，然后
将各个子问题的解合并在一起，从而得
到原问题的解。
? 分治法的一般的算法模式为：
? Divide-and-Conquer(P)
? {//|P|<=n0表示 P的规模不超过阈值 n0，可直接求解
? if (|P|<=n0) return Adhoc(P);
? divide P into smaller subinstants P1,..,Pk;
? for (i =1; i <= k; i++)
? yi = Divide-and-Conquer(Pi);
? return Merge(y1,…,y k);
? } //算法 Merge(y1,…,y k)表示将子问题的解合成 P的解
2010-5-14 计算机算法设计与分析 22
递归算法的时间复杂性
? 一般的，递归的时间复杂性可归结为递归方程：
1 n = 1T(n) ≤
aT(n~b) + D(n) n＞ 1
? 其中,a是子问题的个数,b是递减的步长,~
表示递减方式,D(n)是合成子问题的开销。
? 通常, 递归元的递减 方式 ~有两种：
1、减法，即 n – b,的形式
2,除法，即 n / b,的形式
2010-5-14 计算机算法设计与分析 23
递归算法的时间复杂性
? 若 ~为减法，即 n – b,则有,
T(n) = aT(n – b) + D(n)
= a(aT(n – 2b) + D(n – b)) + D(n) = ??
k–1?
i=0
= akT(1) + ai D(n – ib) = ak + ai D(n – ib)k–1?
i=0
? 这里 k = n / b。 不失一般性令 b = 1,则 k = n。
若设 D(n)为常数，则有 T(n) = O(an)。 即这种情
况下递归算法的时间复杂性为指数函数。
2010-5-14 计算机算法设计与分析 24
递归算法的时间复杂性
? 若 ~为除法，即 n / b,则有,
T(n) = aT(n / b) + D(n)
= a(aT(n / b2) + D(n / b)) + D(n) = ??
k–1?
i=0
= akT(1) + ai D(n / bi) = ak + ai D(n / bi)k–1?
i=0
? 这里 bk = n,所以 k = log b n。 于是：
ak = a = n = np,这里 p = log b a。logb n logb a
? 由此可知,T(n)的首项是 n的常数幂。
2010-5-14 计算机算法设计与分析 25
递归算法的时间复杂性
? 若递减方式为 n / b,则递归算法的时间复杂性
T(n) = np + ai D(n / bi)k–1?
i=0
这里 p = log b a。
? 这个递归方程的首项成为 np称为 ji齐次解，第
二项称为特解。特解一般很难估计。但是，对
于一些特殊的 D(n),可以给出其显式解。
? 一,D(n)为常数 c：
? 这时,ai D(n /bi)k–1?
i=0
c ai，k–1?
i=0
=
∵ ak = np
∴ 对 0 ? i < k有
ai = nj 且 j < p。
ai = nj 且 j < p。
? 这是低于 p次的多项式, 所以 T(n) = O(np)。
2010-5-14 计算机算法设计与分析 26
递归算法的时间复杂性
? 二,D(n)为线性函数 cn：
? 这时,ai D(n /bi)k–1?
i=0
ai(cn/bi)k–1?
i=0
= = cn (a/b) i
k–1?
i=0
(I)
? ⑴ 若 a = b,则 a / b = 1,从而 (I)式为 cnk
又 k = log b n,p = log b a = 1,因此有
T(n) = np + cnk = n + cnlog b n = O(nlog b n)
2010-5-14 计算机算法设计与分析 27
递归算法的时间复杂性
? 二,D(n)为线性函数 cn：
? 这时,ai D(n /bi)k–1?
i=0
ai(cn/bi)k–1?
i=0
= = cn (a/b) i
k–1?
i=0
(I)
? ⑴ 若 a = b,则 a / b = 1,从而 (I)式为 cnkT(n) = O(nlog b n)
? ⑵ 若 a ? b,则 (I)式为 cn((a/b)k – 1)/(a/b – 1)
又 (a/b)k = ak / bk = np / n ∵ bk = b log n = n log b= nb b
令 c / (a/b –1)为 c’,则 (I)式为 c’np –c’n, 从而
T(n) = c1np + c2n,这里 c1 = 1+ c’,c2 = –c’ 。
2010-5-14 计算机算法设计与分析 28
递归算法的时间复杂性
? 二,D(n)为线性函数 cn：
? 这时,ai D(n /bi)k–1?
i=0
ai(cn/bi)k–1?
i=0
= = cn (a/b) i
k–1?
i=0
(I)
? ⑴ 若 a = b,则 a / b = 1,从而 (I)式为 cnkT(n) = O(nlog b n)；
? ⑵ 若 a ? b,则 T(n) = O(np + n)；
显然：
若 a < b,p = log ba < 1,np < n，
反之,若 a > b,则 np > n。
?①若 a < b,则 T(n) = O(n)；
?②若 a > b,则 T(n) = O( p)。
2010-5-14 计算机算法设计与分析 29
递归算法的时间复杂性
? 总之，当 D(n)线性函数 cn时，递归算法
的时间复杂性为：
T(n) =
O(n) 当 a < b时
O(nlogbn) 当 a = b时
O(np) 当 a > b时
其中,p = log ba。
2010-5-14 计算机算法设计与分析 30
递归算法的时间复杂性
? 二,D(n)为 n的高次幂，即 D(n) = nx：
? T(n) = ai D(n /bi)k–1?
i=0
ak + ai(n/bi)xk–1?
i=0
= ak +
∵ n = bk ∴ (n/bi)x = (bk–i)x = (bx)k–i = D(b)k/ D(b)i= D(b k (a/D(b))ik–1?
i=0
ak +
? ⑴ 若 a = D(b),则
∵ a / D(b) = 1
∴ T(n) = ak + akk = np(1 + log bn) = O(nplog bn)
T(n) = O(nplog bn)
2010-5-14 计算机算法设计与分析 31
递归算法的时间复杂性
? 二,D(n)为 n的高次幂，即 D(n) = nx：
? T(n) = ai D(n /bi)k–1?
i=0
ak + ai(n/bi)xk–1?
i=0
= ak +
= D(b)k (a/D(b))ik–1?
i=0
ak +
? ⑴ 若 a = D(b),则 T(n) = O(nplog bn)
? ⑵ 若 a ? D(b),则
T(n) = ak + D(b)k(ak/ D(b)k – 1)/(a/ D(b) – 1)
= c1ak +c2D(b)k = c1nlog a + c2nlog D(b) b b
其中,c1 = 1 + 1/(a/D(b) – 1),c2 = 1/(1 – D(b))
T(n) = O(nlog a + nlog D(b) )b b
2010-5-14 计算机算法设计与分析 32
递归算法的时间复杂性
? 二,D(n)为 n的高次幂，即 D(n) = nx：
? T(n) = ai D(n /bi)k–1?
i=0
ak + ai(n/bi)xk–1?
i=0
= ak +
= D(b)k (a/D(b))ik–1?
i=0
ak +
? ⑴ 若 a = D(b),则 T(n) = O(nplog bn)
? ⑵ 若 a ? D(b),则 T(n) = O(nlog a + nlog D(b) )b b
∵ D(b) = bx,∴ log bD(b) = log bbx = x
若 a > D(b),则 log ba > log bD(b),即 p > x。
反之，则 p < x。
?于是
①若 a < D(b),则 T(n) = O(n)；
②若 a > D(b),则 T(n) = O(np)。
2010-5-14 计算机算法设计与分析 33
递归算法的时间复杂性
? 总之，当 D(n)幂函数 nx时，递归算法的时
间复杂性为：
T(n) =
O(nx) 当 a < D(b)时
O(nplogbn) 当 a = D(b)时
O(np) 当 a > D(b)时
其中,p = log ba。
2010-5-14 计算机算法设计与分析 34
求解递归方程
? 考虑下列递归方程,T(1) = 1
? ⑴ T(n) = 4T(n/2) +n
? ⑵ T(n) = 4T(n/2) +n2
? ⑶ T(n) = 4T(n/2) +n3
? 解：方程中均为 a = 4,b = 2,其齐次解为 n2。
? 对⑴,∵ a > b1 (D(n) = n) ∴ T(n) = O(n2)；
? 对⑵,∵ a = b2 (D(n) = n2)∴ T(n) = O(n2logn)；
? 对⑶,∵ a < b3 (D(n) = n3) ∴ T(n) = O(n3)；
2010-5-14 计算机算法设计与分析 35
求解递归方程
? 考虑递归方程, T(n) = 1 n = 12T(n/2) +nlog n n > 1
? 解,∵ a = b = 2∴ 齐次解为 n。
? 因 D(n) = nlogn,非幂函数，只好将 T(n)展开,
? T(n) = ai D(n /bi)k–1?
i=0
ak + 2i (n /2i)log(n /2i)k–1?
i=0
n +=
nlog(n /2i)k–1?
i=0
n += n(logn –log2i )k–1?
i=0
n += ilog2)
= n + knlog n – n(k – 1)k/2nk2/2 + nk/2 又 k = log n
= n + (nlog2n)/2 +(n logn)/2 = O(nlog2n)
2010-5-14 计算机算法设计与分析 36
二分搜索有序表的算法分析
? Binary-Search(L,n,z)
? {k = 1; m = n; //*k和 m分别为搜索部分的首和尾
? flag = 0; //*找到标志初始为 0
? while (k <= m && flag = 0) {
? j = ?(k + m) / 2? ; //*取中点下标
? if (z == L[j]) flag = 1 //* 找到了标志为 1
? else if (z < L[j]) m = j – 1 //*小于中点，尾前移
? else k = j + 1 //*大于中点，首后移
? }
2010-5-14 计算机算法设计与分析 37
二分搜索有序表的算法分析
[n]
[n/2] [n/2]
[n/4] [n/4] [n/4] [n/4]
?? ?? ??
[1] [1] [1] [1]??
?log n? + 1
? 二分搜索的每次循环查找区间减半，查找区间
构成一棵二叉树，最坏的情况是一直走到二叉
树的叶子。因此算法的复杂度为 log n + 1。
2010-5-14 计算机算法设计与分析 38
二分搜索有序表的算法分析
? 我们也可以证明二分搜索的算法复杂度
为 logn + 1。
W(n) = W(?n/2? ) + 1 n > 1 1 n = 1
? 显然，我们有：
? 于是我们可以对 n进行归纳证明有：
W(n) = ?log n? + 1
2010-5-14 计算机算法设计与分析 39
二分搜索有序表的算法分析
? 归纳证明 W(n) = ?log n? + 1。
? 证明：归纳基础：当 n = 1,有
W(n) = 1 = ?log 1? + 1= ?log n? + 1
? 归纳假设：对 1 ? k < n 有 W(k) = ?log k? + 1。
? 于是有：
? W(k) = W( ?n/2? ) + 1 (∵ ?n/2? < n )
? = ( ?log ?n/2?? + 1) + 1
当 n为偶数时,?n/2? = n/2；
当 n为奇数时,?n/2? = (n – 1) / 2。
所以，
log ?n/2? = log n – 1 若 n为偶数log (n – 1) – 1 若 n为奇数
? 所以,无论如何总有,W(n) = ?long n?+ 1二分搜索算法的时间复杂度为 O(log n)。
2010-5-14 计算机算法设计与分析 40
大整数的乘法
? 设 X和 Y都是 n位的二进制整数。如果用常规的
乘法计算乘积 XY,其时间复杂性为 O(n2)。
? 将 X和 Y都分成 2段，即
X = A2n/2 + B,Y = C2n/2 + D
? 于是, XY = (A2n/2 + B)(C2n/2 + D)
= AC2n +(AD+BC)2n/2 + BD
? 这样有, T(n) = 4T(n/2) + O(n)
因为 a = 4 > D(b) = 2,所以
= O(nlog4))2
无效果！
将 XY改写成：
XY = AC2n +(A–B)(D–C)+AC+BD)2n/2 + BD
? 这样有, T(n) = 3T(n/2) + (n)
同样因为 a = 4 > D(b) = 2,所以
( l 3 )1.59
2010-5-14 计算机算法设计与分析 41
Strassen矩阵乘法
? 矩阵乘法的时间复杂性为 O(n3)。
? 如果将矩阵分为 4个大小相等的子矩阵，则
C11 C12
C21 C22 =
A11 A12
A21 A22
B11 B12
B21 B22
? C11 = A11B11 + A12B21 C12 = A11B12 + A12B22
? C21 = A21B11 + A22B21 C11 = A21B12 + A22B22
? 这样有, T(n) = 8T(n/2) + O(n2)
因为 a = 8 > D(b) = 22 = 4,所以
= O(n log8)) 3
也无效果！
2010-5-14 计算机算法设计与分析 42
Strassen矩阵乘法
? 若改为,
M1 = A11(B12 – B22) M2 = (A11 + A12)B22
M3 = (A21 + A22)B11 M4 = A22(B21 – B11)
M5 = (A11 + A22) (B11 + B22)
M6 = (A12 – A22) (B21 + B22)
M7 = (A11 – A21) (B11 + B12)
C11 = M5+M4–M2+M6 C12 = M1 + M2
C21 = M3 + M4 C11 = M5+M1–M3 –M7
? 这样有, T(n) = 7T(n/2) + O(n2)≤ O(n log7 )2.82
? 目前的结果为, O(n2) ≤ O(n2.376)
2010-5-14 计算机算法设计与分析 43
棋盘覆盖问题
? 一个 2k× 2k的特殊棋盘是其中含有一个特殊方
格的棋盘，如左下图为 k=2的一个特殊棋盘。
? 现在任意给定一个 2k× 2k的特殊棋盘，要用右
下图所示的 L型骨牌来无重叠的覆盖它。
1
11
2
2 2
3 3
3
4
4 4
5
55
在 2k× 2k的棋
盘覆盖中要用
到 (4k–1)/3个 L
型骨牌。
2010-5-14 计算机算法设计与分析 44
棋盘覆盖问题的分析
? 当 k>0时，将 2k× 2k的棋盘分割成 4个 2k–1× 2k–1
的子棋盘，如右下图所示：
2k–1× 2k–1 2k–1× 2k–1
2k–1× 2k–1 2k–1× 2k–1
? 特殊方格必定位于 4个子棋盘之一中。
然而，这样一来四个子棋
盘的情形就不一致了。因
为递归求解是将问题归结
到较小的规模的同一问题，
所以就需要将三个正常子
棋盘也转化成特殊棋盘。
为此，可以用一个 L型骨
牌来覆盖其余三个子棋盘
的会合处，如左图所示。
这样原问题转化成了四个
较小规模的子问题。递归
地分割下去直至单格棋盘。
2010-5-14 计算机算法设计与分析 45
棋盘覆盖的算法
? 棋盘覆盖 (参数表 ) {
? 如果是单个格子，则返回；
? 将棋盘划分成尺寸为一半的子棋盘；
? 判断特殊方格在哪个子棋盘中，再用相应的
L型 骨牌覆盖相应结合部，即不含特殊方格的
部分在结合部的三个方格；并记下它们的位置，
作为个部分的特殊方格；
? 依次对左上角、右上角、左下角和右下角这
四个子棋盘进行棋盘覆盖； }
2010-5-14 计算机算法设计与分析 46
棋盘覆盖算法中的参数
参数表中应有哪些参数呢？? 递归元：棋盘尺寸 size=2k。 递归时棋盘尺寸减
半，即 size=size/2； 当 size为 1时递归终止。
? 表示棋盘位置参数，即棋盘左上角方格的列
行号 tr和 tc,每次用 size/2调整子棋盘位置。
? 表示特殊方格位置的参数，即特殊方格的行
号 dr和列号 dc。
? 棋盘用一个二维整型数组 Board表示。
? L型骨牌覆盖的顺序用全局变量 tile表示。
请同学们自己用设计程序实现此算法。
2010-5-14 计算机算法设计与分析 47
棋盘覆盖算法的正确性
? 要证明一个算法的正确性，需要证明两点：
? (1)算法的部分正确性；
? (2)算法的终止性。
? 下面我们用归纳法证明棋盘覆盖算法的部分正
确性：
归纳基础：对尺寸为 21的特殊棋盘，无论特殊
方格在什么位置，显然都可正确覆盖。
? 假设对尺寸 2k–1的特殊棋盘均可正确覆盖。
? 对尺寸 2k的特殊棋盘，算法划分为四个尺寸为
2k–1的子棋盘，再用一块 L型骨牌覆盖三个正常
子棋盘的结合处后，恰好形成四个尺寸 2k–1的
特殊棋盘，由归纳假设，它们均可正确覆盖。
因而也正确覆盖了尺寸 2k的特殊棋盘。
? 由归纳法可知，棋盘覆盖算法是部分正确。
算法的终止性：
递归的终止条件为递归元 size为 1时递归终止。
递归元 size的初值为 2k。 每次递归时递归元减
半，即 size=size/2； 因此，必然在有穷步内递
减为 1。
? 所以此算法必定终止。
? 由部分正确性和终止性可知，此算法是完全正
确的。
2010-5-14 计算机算法设计与分析 48
? 设 T(k)是棋盘覆盖算法覆盖 2k× 2k的棋盘所需
要的时间，则从算法的分治策略可知,T(k)满
足如下递归方程：
棋盘覆盖算法的复杂性
T(k) = O(1) k = 04T(k–1) + O(1) k＞ 0
? 递归元递减方式是减法 k – 1,a = 4,因此
T(k) = O(4k)。
? 由于覆盖 2k× 2k的棋盘要用 (4k–1)/3个 L型骨牌，
故此算法是一个在渐进意义下最优的算法。
2010-5-14 计算机算法设计与分析 49
最接近点对问题
? 给定平面上 n个点，在 n个点组成的所有点对中，
找出其中相互距离的最小一对点。
? 此问题的简单解法是，算出每个点与其它 n–1
个点之间的距离，再找出其中距离最小的一对
点。这样做的时间复杂性为 O(n2)。
? 下面用分治法构造一个时间复杂性为 O(nlogn)
的算法。
? 为此我们先考虑一维的情况：
2010-5-14 计算机算法设计与分析 50
一维最接近点对
? 设 S为 x轴上 n个点的集合，求 S中最接近点对。
? 假设用 x轴上某个点 m划分 S为 S1和 S2,使得
S1={x∈ S | x≤m},S2={x∈ S | x＞ m}。
m
S1 S2
? 递归地在 S1和 S2中找出其最接近点对 {p1,p2}
和 {q1,q2},并设 d = min{|p1,p2|,|q1,q2|}
p1 p2 q1 q2
? 易知,S中最接近点对是 {p1,p2}或 {q1,q2}，
或 {p3,q3},这里 p3=max{S1},q3 =min{S2}。
p3 q3
2010-5-14 计算机算法设计与分析 51
一维最接近点对算法
? bool Cpair1(S,d)
? {
? n = |S|;
? if (n < 2) { d = ∞; return false }
? m = S中各点的坐标的中位数；
? 构造 S1和 S2; // S1={x?S | x?m},S2={x?S | x>m}
? Cpair1(S1,d1);
? Cpair1(S2,d2); //分别求 S1和 S2的最接近点对
? p=max{S1}; q =min{S2}; d = mim{d1,d2,q – p};
? return true
? }
2010-5-14 计算机算法设计与分析 52
一维最接近点对算法复杂性
? 如果对 S的分割不平衡的话，最坏的情况是 S1
仅含一个点，这时算法的复杂性为 O(n2)。
? 所以要采用中位数 m来分割 S。
? 该算法的分割步骤和合并步骤总共耗时 O(n)，
因此算法耗时满足递归方程
T(n) = O(1) n＜ 02T(n/2) + O(n) n≥4
? 因为 a = 2 = D(b),可知 T(n) = O(nlogn)。
2010-5-14 计算机算法设计与分析 53
平面最接近点对
? 做一条直线 L,x=m,将 S分割为 S1和 S2,其中
m为所有点的 x坐标的中位数。递归地求得 S1
和 S2中的最小距离 d1和 d2，令 d=min{d1,d2}。
L
S1 S2d1 d2
? 但是 S1和 S2之间的最小距离却需要考察 S1和 S2
在 l两侧距离不超过 d的区域 P1和 P2间的点对。
d
P1
d
P2
? P1和 P2间的点对均为最近点对
的候选，最坏情况有 n2/4个。
? 而实际上，对 P1中的任意一点，
最多只需要考察 P2中的 6个点。
2010-5-14 计算机算法设计与分析 54
最多只需要考察 6个点
? 考虑 P1中的任意一点 p,它若与 P2中的点 q构成
最接近点对，则其距离必定小于 d。 这样的点
必定落在一个 d× 2d的矩形 R内：
d
d
P1 P2
p
R
L
? 在矩形 R中最多有 6个点。? 不然的话，可以将矩形 R分
成 6个 (d/2)× (2d/3)个小矩形，
? 每个小矩形对角线的长度为
5d/6。 (d/2)2+(2d/3)2=25d2/36
? 若 R中有 6个以上的点，则必
有两点 u,v在同一小矩形内，
于是 |uv|＜ 5d/6。 矛盾。
所以 R中至多有 6个点，即对
P1中的每个点至多只需要考
察 P2中的 6个点就可以了。
? 分别将 P1和 P2中的点按 y坐
标排序；再对 P1中的每个点
p,考察 P2中 y坐标在 y(p)± d
范围内的点 (最多 6个 )。
2010-5-14 计算机算法设计与分析 55
平面最接近点对的算法
? bool Cpair2(S,d)
? { n = |S|;
? if (n<2) { d = ∞; return false}
? m = S中各点 x坐标的中位数；构造 S1和 S2；
? Cpair2(S1,d1); Cpair2(S2,d2); dm=min(d1,d2)
? 构造 P1和 P2；
? //P1={p|m–dm?x(p)?m},P2={q|m<x(q)?m+dm}
? 将 P1和 P2中的点按 y坐标值排序；
? 依次扫描 P1中点 u并计算 u与 P2中 y坐标在 y(u)± dm
范围内的点 (最多 6个 )；设 dl是这样找到的最小距离；
? d = min(dm,dl);
? return true }
2010-5-14 计算机算法设计与分析 56
最接近点对的算法复杂性
? 在算法中：
? 计算中位数和 min需时为常数。
? 将 S分割为 S1和 S2需时为 O(n)。
? 在排序后的 P1和 P2中找最小距离 dl需时为 O(n)。
? 对 P1和 P2排序在最坏情况下需时 O(nlogn),这
不符合要求。
若在整个算法开始之前对各点的 y坐标进行一
次预排序，则在递归中就无须再排序，只要对
P1或 P2进行线性扫描即可，需时仍为 O(n)。
? 由此易知递归需时为 O(nlogn),预排序需时为
O(nlogn),因而整个算法需时为 O(nlogn)。
2010-5-14 计算机算法设计与分析 57
分治法总结
? 分治法的基本做法是：
? (1)将规模为 n的问题分解为 k个规模较小的子问
题。这些子问题相互独立且与原问题相同。
? (2)递归地解这些子问题。
? (3)然后将子问题合并得到原问题的解。
? 分治法的时间复杂性：
? 子问题的复杂性当然低于原问题。但是整体上
能否降低复杂性还取决于合并。通过降低合并
的复杂性可以降低原问题求解的复杂性。
