算法导论
Chapter 1 Introduction
1.1 Role of Algorithms in Computer Science
(1) 算法是计算机科学基础的重要主题
?70年代前，计算机科学基础的主题没有被清楚地认清。
?70年代，Knuth出版了《The Art of Computer Programming》(三
卷), 以各种算法研究为主线，确立了算法为计算机科学基础的
重要主题，1974年获得图灵奖。
?70年代后，算法作为计算机科学的核心推动了计算机科学技术的
飞速发展
(2) 计算机科学的体系
?解决一个计算问题的过程
可计算否?能行可计算否?算法设计与分析?用计算机语言实现算法?软件系统
?可计算理论:
?计算模型
?可计算问题/不可计算问题
?计算模型的等价性--图灵/Church命题
?计算复杂性理论
?在给定的计算模型下研究问题的复杂性
?上界
?下界
?平均
?固有复杂性
?复杂性问题的非类: P=NP?
?抽象复杂性研究
?算法设计和分析
?可计算问题的算法的设计与分析
?设计算法的理论、方法和技术
?分析算法的理论、方法和技术
(3) 算法设计与分析的意义
?计算机各领域的核心
1
?计算机工程特别是计算机软件工程的基础
1.2 Concepts of Algorithms (1) 算法的定义
定义1.2.1 (计算). 可由一个给定计算模型机械地执行的规则或计算步骤序列称为该计算模型的一个计算。
*一个计算机程序是一个计算(计算模型是该计算机)
*计算可能永远不停止--不是算法。
定义1.2.2 (算法). 算法是一个满足下列条件的计算:
? 有穷性/终止性:有限步内必须停止。/* 好算法/坏算法 */
? 确定性:每一步都是严格定义和确定的动作。 /* 要严格算法语言 */
? 能行性:每一个动作都能够被精确地机械执行。
? 输入:有一个满足给定约束条件的输入。
? 输出:满足给定约束条件的结果。
*直观地说，算法如下图所示:
输出输入F
*算法的目的是求解问题。什么是问题,
(2) 问题的定义
定义1.2.3 (问题). 设Input和Output是两个集合。一个问题是一个关系R,Input，Output，Input称为问题R的输入集合，Input的每个元素称为R的一个输入，Output称为问题R的输出或结果集合，Output的每个元素称为R的一个结果。
*问题定义了输入和输出的关系。
例. SORT问题定义如下:
输入集合Input={
| a是整数} 12ni
输出集合Output={ | b是整数, b,b,…,b} 12ni12n
问题SORT={(，)| ,Input, 1n1n1n1n
}={b, …, b}}. ,Output, {a, …, a1n1n
定义1.2.4 (问题实例). 问题R的一个实例是的一个二元组。
2
*一个算法面向一个问题，而不是仅仅求解一个问题的实例。
(3) 算法实例—Insertim Sort
,问题定义
Input=, , a是整数, 12ni
output=, , b是整数,且b,b,...,b, 12ni12n
R=,(,) , ,Input,,output, 1n1n1n1n
,a,...,a,=,b,...,b, 1n1n,算法的思想—扑克牌游戏
,算法描述
Insertion-sort(A)
Input: A,1,.....,n,=n个sort数
output: A,1,.....,n,=n个sort数
Method:
FOR i=2 To n Do
key,A,i,,
i,j-1
WHILE i>0 AND A,i,>key Do
A,i+1,, ,i,;
i,i-1;
A,i+1,,key;
,实例: A,1,......,n,=5,2,4,6,1,3
1.3 Analyzing Algorithms
(1) 正确性分析
定义1.3.1. 一个算法是正确的，如果它对于每一个输入都最终停止,而且产生
正确的输长
*不正确:?不停止(在某个输入上)
?对所有输入都停止，但对某个输入产生不正确的结果
*近似算法 ?对所有输入都停止
?产生近似正确的解或产生不多的不正确解
*正确性证明
,证明算法对所有输入都停止
,证明对每个输入都产生正确结果
3
*调试程序,程序正确性证明
―程序调试只能证明程序有错误，不能证明程序无错误‖
(2) 复杂性分析
目的:预测算法对不同输入所需要的资源量—是输入大小的函数
复杂性测度:时间，空间， I/O等等
用途:为求解一个问题选择最佳算法
需要的数学基础:离散数学，组合数学，概率论，代数等
需要的数学能力:,建立算法复杂性的数学模型
,数学模型化简
定义1.3.2(输入的大小) 设Input是问题R的输入集合，R的输入大小是一个函数。F:Input,N，N是正整数集合
例: 矩阵问题的输入大小=矩阵的维数
图论问题的输入大小=图的边数/结点数
定义1.3.3(时间复杂性)一个算法对特定输入的时间复杂性是该算法对该输入产生结果需要的原子操作或“步”数
*时间复杂性是输入大小的函数
*我们假设每一步的执行需要常数时间，实际上每步需要的时间量可能不同。
定义1.3.4(空间复杂性) 一个算法对特定输入的空间复杂性是该算法对该输入产生结果所需要的存储空间大小。
定义1.3.5(最坏复杂性)设Input是问题R的输入集合，Complexity(X)是求解R的算法A的复杂性函数，Size(y)是R的输入大小函数，A的最坏复杂性是
Max,Complexity(size(y)),y,Input,
定义1.3.5(最好复杂性)Mix,Complexity(size(y)),y,Input,
, 定义1.3.6 (平均复杂性)设y?Input,y作为算法A的输入出现的概率是
p，complexity(size(y))p，A的平均复杂性为. y,yy,Input
1.4 Designing Algorithms (1) 算法设计的方法
4
?divide-and-conguer
?Dynamic Programming
?Grcedy Algorithms
?Amortized Aralysis
?Approximation Alorithms
?Randomlized Alorithms
(2) 不同的设计方法有不同的分析方法
第二章 算法分析的数学基础
outline
1 算法复杂性的阶
2 和式的估计与界限
3 递归方程
4 集合、关系、函数、图、树等
5 计数原理和概率论
2.1 复杂性函数的阶
2.1.1同阶函数集合
5
定义2.1.1(同阶函数集合). ,(f(n))={g(n)|，c,c>0,n,当n, 120 ,cf(n),g(n),cf(n)}称为与f(n)同阶的函数集合。 0 12n
*如果g(n),,(f(n)),我们称个g(n)与f(n)同阶。
*g(n),,(f(n))常记作g(n)=,(f(n))。
*f(n)必须是极限非负的，即当n充分大以后，f(n)是非负的，否
则=空集。 ,(())fn
22fnanbncn()(),，，,, 例1 证明
222cnanbnccn,，，, 证. 设 ，令c=a/4, c=7a/4,则 1212
a7222， ,，，,nanbncan44
222cnanbnccn,，，, 令。当时成立。 nn,nbaca,,2max,，，12，，00
326nn,,() 例2 证明
32 证. 如果存在c、c>0，n使得当n,n时，c,6n,cn。于是，当12 0012n>c/6时，n,c/6，矛盾。 22
didpnann()(),,, 例3 ,i,0i
6
0 例4 因任何常数cn,,,,()()1，，如果令 ccc,,12
13 。 ccccn,,,,,112022
2.1.2 低阶函数集合
定义2.1.2(低阶函数集合). O(f(n))={g(n)|，c>0,n,当n, 0
,0,g(n),cf(n)}称为比f(n)低阶的函数集合。 0 n
*如果g(n),O(f(n)),称f(n)是g(n)的上界。
*g(n),O(f(n))常记作g(n)=O(f(n))。
例1 ,(g(n)),f(n),f(n),O(g(n))
,(g(n)),O(g(n))
2nn,;() 例2 证明 。
2证. 令c=1,n=1,则当时，。 nn,0,n,cn00
2.1.3 高阶函数集合
定义2.1.3(高阶函数集合). ,(f(n))={g(n)|，c>0,n,当n, 0
,0,cf(n),g(n)}称为比f(n)高阶的函数集合。 0 n
7
*如果g(n), ,(f(n)),称f(n)是g(n)的下界。
*g(n),,(f(n))常记作g(n)=,(f(n))。
定理2.1.对于任意f(n)和g(n), iff fngn()(()),,fngn()(()),,而且f(n)=,(g(n)).
证. 如果, 则 当时, ,fngn()(()),,，,,ccn,,,00nn,1200
. cgnfncgn()()(),,12
显然. f(n),,(g(n)) and f(n),,(g(n))
, 如果且,则由可 fngn()(()),,fngn()(()),,fngn()(()),,
知，存在使得，当，。由 cn,,,0nn,fncgn()(),1111
f(n)=,(g(n))可知，使得当， ，,cn,,0nn,fncgn()(),2212
nnn,max, 令,则当，cfnfncgn()()(),,。 nn,,,012210
2.1.4. 严格低阶函数集合
;(())(),,gnfncn,,,，,00定义2.1.4(严格低阶函数集合). ,00,,fncgn()() for all }称为严格比g(n)低阶的函数集合。 nn,0
*如果f(n),o(g(n)),称g(n)是f(n)的严格上界。
8
*f(n),o(g(n))常记作f(n)=o(g(n))。
22nn,;() 例1. 证明
222,,c02,cn 证. 对, 欲，必，即。所以，当时，2ncn,n,,n0cc
2,,c0对，n,n。 2ncn,0
222nn,;() 例2(证明
22证. 当c=1>0时，对于任何, 当，都不成立 nnn,2n,cn00
fn()fngn()(())lim,,,;0.1. 命题2n,,gn()
证.由于f(n)=o(g(n)), 对任意,>0,存在，当时, nnn,00
0,f(n)<,g(n),
fnf(n)()0,,,,0即. 于是, . limn,,gng(n)()
2.1.5 严格高阶函数集合
wgnfncn(())(),,,,，,00 定义2.1.4(严格高阶函数集合). ，,0
nn,0,cg(n),f(n) for all 称为严格比g(n)高阶的函数集合。 ,0
命题2.2. f(n),w(g(n)) iff g(n),o(f(n)).
9
证:
,,c0, 对，1/c>0. 由知, 对1/c>0,,当fnwgn()(()),，nnn,00时,(1/c)g(n)0, 1/c>0.由可知, 当时, gnfn()(()),;，,n0,nn,00g(n)<(1/c)f(n)，即cg(n)0,cn2c.令n=2c+1, 则当n,n, cncg(n),即当n,n时,f(n)/g(n)>c. 于是, . 0n,,g(n)
2.1.6 函数阶的性质
10
A传递性:
(a) fngngnhnfnhn()(())()(())()(()),,,,,,,,
(b) fngngnhn()(())()(()),,,,,,,fnhn()(()),
(c) fngngnhn()(())()(()),,,,,,,fnhn()(()),
(d) f(n),o(g(n)),g(n),o(h(n)),f(n),o(h(n))
(e) . fnwgngnwhn()(())()(()),,,,,fnwhn()(())
B 自反性:
(a) ， fnfn()(()),,
(b) ， fnfn()(()),,
(c) . fnfn()(()),,
C 对称性
. f(n),,(g(n))gnfn()(()),,iff
D 反对称性:
f(n),O(g(n)) gnfn()(()),, iff
fngn()(()),; gnwfn()(()), iff
*并非所有函数都是可比的，即对于函数fn()和，可能gn()
1，sinnnfngnfngn()(()),()(()),,,,. 例如, 和. n
2.2
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
符号和通用函数
11
2.2.1 Flour和ceiling
x定义2.2.1(Flours和ceiling). 表示小于或等于x的最大整数. ，，x表示大于等于x的最小整数. ，，
xxxxx,,,,,，11 命题2.2.1 ，，，，
nnn22，, 命题2.2.2 对于任意函数n, ，，，，
nn，，，，nk,2nk2,,k，,,nkn22 证. 若,则，. 于是 ，，，，,,,,22,,,,
n，，，,，，,，,nkkkn2121 若 n=2k+1, 则. ，，,,2,,
命题2.2.3 设n、a、b是任意整数，，则 ab,,00,
(1) nabnab,。 ，，，，，，
nabnab,(2) ，，，，，，
n/akbkabn，，，，，，，，nkab, 证. (1) 若,则。 ,,k,,,,,,,,,,bbabab,,,,,,,,
若，0<，则 nkab,，,,,ab
nkb，1，，nkab，，，，，,，，，， = ,,k，1b,,，k1,,,,,,,,,,abab,,,,ab,,,,,,
12
(2) 类似于(1)的证法。
2.2.2 多项式
didPnann()(),,, 命题2.2.4 ,其中 a,0,id,0i
ddiddiddanann,,,() 证. 由于，，所以an,(d，1)max{a}n,O(n),ii,idi,00i,
didPnann()(),,,。 ,i,0i
kfnn()(),, 定义2.2.2 如果如果 ，则城是多项式界限的。 fn()
2.3 和
2.3.1 求和公式的性质
1 线性和
nnn
cabcab，,，命题2.4.5 ，，,,,kkkk,,,111kkk
nn,, 命题2.4.6 ,,(())()fkfk,,,,,,,k,,11k
13
证. 对n用数学归纳法证明。
n,1nm, 当时，显然成立。假设时成立。 ,,(())(())ff11,
m，1m
nm,，1,,,(())(())(())fkfkfm,，，1 令，则 ,,k,1k,1
m,, ,,,fkfm()(())，，1,,,,,k,1
m,, ,，，,fkfm()()1,,,,,k,1
m，1,, 。 ,,fk(),,,,,k,1
2. 级数
nnn，()12i,,,n() 命题2.4.7 ,2i,1
1n，nx,1k2nxxxx,，，，，,1.....x,1 命题2.4.8 ，，,x,10k,
,1kx,x,1 ,1,xk,0
n1H,,ln 命题2.4.9 n，,()1 ,nkk,1
n
aaaa,,, 命题2.4.10 . ，，,kk,1n0k,1
n,1
aaaa,,, 命题2.4.11 ，，,kk，10nk,0
n,1n,11111,,,,,,1 命题2.4.12 ,,,,,,kkkkn()，，11k,1k,1
nnlg(a)lga命题2.4.13 , ,,kkk,1k,1
14
3 和的界限
?数学归纳法证明
nkn33,,() 例1. 证明 ,k,0
nkn33,c 证明对于c,2/3, 存在一个,当时. 证nnn,0 ,0k,0
nnk31,,c 当n=0时, =c3. ,k,0
nm,，1 设n,m时成立. 令,则
m，1m11,,kkm，1mm，1m，1m，1 cc. ,，,，,，333333,c3,,,,c3k,0k,0,,
n
kn,,() 例2. 错误证明: ,k,1
1n，1n
n,1k,,11,()kknnnn,，，,，，,()()()()11,, 证. 时,,. ,,,k,1k,1k,1
*错在O(n)的常数c随n的增长而变化，不是常数。
nn
kn,,()kcn,() *要证明需要证明: 对某个c>0, . ,,k,1k,1
?直接求和的界限
nn2knn,,例1. ,,k,,11k
n
an,maxa 例2. ，. ,,,ki1k,
15
n
k,0a 例3. 设对于所有,，求的上界. aar,,1,kkk，1k,0
解:, aaraar,,,1010
2aaraarar,,,, , 21210
3aaraarar,,,, …… 32320
kaaraarar,,,, kkkk,,110
n,,akk0aarar,,, 于是, . ,,,00k1,r000k,,kk,
,kk3 例4. 求 的界 ，，,k,1
kkk，11，1112,,,,,，1,,r 解. 使用例3的方法. . 于是 ,,kk，1,,3kk3333
k,,,k1211,,k ,ar,,,,1. ,,,,,1k2333111k,k,k,3,,1,3
n 例5. 用分裂和的方法求k的下界. ,k,1
2n2n2nnnn,,2 解: . kkkn,，,，,02,,n,,，，,,,,,,,2k,,,，,,，11kkn211kkn21
2,k 例6. 求 的上界 ,k2k0,
16
2()k，12k，1()k，182k,3 解:当时, ,,22k2k9k2
k222,,,298kkk,, 于是 1=O(1). ,，,，,,(),,,,,,kkk,,89222,,,,k0k0kk33
n1 例7. 求的上界 H,,nkk,1
n11111111,,,,,，，，，，， 解:,,,,,,,,,k1234567k,1
11111111,,，，，，，，，，， …… ,,,,89101112131415
iinnnlogloglog,,2121，，，，，，111logn1(logn) ,,，,, ,,,,,,,iii,ij,,10ij,,12j00，2
nnn，1fxdxfkfxdx()()(),, 例8. 如果单调递增, 则. fk(),,,m,1mkm,
f(x)
f(x)
17
m-1 m m+1 m+2 … n
f(x)
,1nnnf(k),f(k),x,f(x)dx , , f(m,1),f(n),x,1,,,,1m,,,1kmkm
n，1nn，1f(k),f(k),x,f(x)dx ,,,k,mk,mm
nn，n1fxdxfkfxdx()()(),, 例9. 当单调递减时,. fx(),,,mm,1km,m-1 m m+1 m+2...n-2 n-1 n n+1
n，1`nnndx11dx.,,lnn 例10. n, . ,,，ln()1,,,,kxk,21kxk,11
2.4 递归方程
递归方程: 递归方程是使用小的输入值来描述一个函数的方程或
18
不等式.
递归方程例: Merge-sort排序算法的复杂性方程:
T(n)=,(1) if n=1
T(n)=2T(n/2)+,(n) if n>1.
T(n)的解是,(nlogn)
求解递归方程的三个主要方法:
?Substitution方法: Guess first,然后用数学归纳法证明.
?Iteration方法: 把方程转化为一个和式,然后用和估计技
术求解.
?Master方法: 求解型为T(n)=aT(n/b)+f(n)的递归方程.
2.4.1 Substitution方法
一般方法: ?猜解的形式
?用数学归纳法证明猜测的解正确
*该方法只能用于解可猜的情况.
1 Make a good guess
不幸:无一般的猜测正确解的方法，需要
19
?经验
?机会
?创造性和灵感
幸运:存在一些启发规则帮助人们去猜测
?Guess方法?:联想类似的已知T(n)
n,,TnT(),2，n 例1. 求解, T(1)=1. ,,,,2
解:展开T(n)若干步,可以猜测T(n)=O(nlogn).
证明T(n)=O(nlogn).
nm, 设时或n=m+1时
m，1m，1m，1,,,,T(m，1),2T，m，1,2Clog，m，1 ,,,,222,,,,
,，，,，，Cmmm()(lg())1111
,(m，1)lg(m，1)，(m，1)(1,C)
,，，,CmmC()lg()111，只要 .
于是,T(n),O(nlgn).
*边界条件的问题:
T(1),c，1，log1,0 设是边界条件，则不成立 T()11,
*边界条件问题的解决
20
我们只要求对于时,.我们只需看n=2 T(n),O(nlogn)nn,0
n n=3，或4等，选一个满足的最小即可。 T(n),c，nlogn0
2,,T(2),2T，2,2，2,4,C，2,log2c,2 ,只需,与上界的 ,,2,,
不矛盾. C,1
n,,T(n),2T，17，n例2. 求解. ,,2,,
nn,,,,T(n),2T，17，nTnT(),2，n 解: 猜测: 与只相差一个17. ,,,,,,22,,
nn,,,,T，17与T 当n充分大时的差别并不大，因为 ,,,,,,,,22
nn 相差小. 我们可以猜. Tnnn()(lg),,，17与22
证明: 用数学归纳法证明. Tnnn()(lg),,
?Guess方法?:猜测loose上、下界，然后减少不确定性范围
n,,TnT(),2，n 例3. 求解. ,,,,2
2TnnTnn()()()(),,,,， 解: 首先证明
然后逐阶地降低上界、提高下界。
,(n)的上一个阶是,(nlogn),
2 O(n)的下一个阶是O(nlogn)。
21
?细微差别的处理
问题:猜测正确，数学归纳法的归纳步似乎证不出来
原因:归纳假设不能充分证明
解决方法:从guess中减去一个低阶项，可能work.
n,,，， 例4. 求解 TnTnT(),，2，1，，,,，，,,,,2,,
解:? 我们猜 Tnn()(),,
T(n),cn2，cn2，1,cn，1,cn 证: ，，，，
证不出 Tncn()(),,
b,0 ? 减去一个低阶项，猜，是常数 Tncnb(),,
,,n1 证:设当时成立
nnn,,，，,,，， ，，T(n),Tn2，T，1,c,b，c,b，1,,，，,,,,,,222,,，，,,,,
b,1 (只要)。 ,cn,2b，1,cn,b,b，1,cn,b
*c必须充分大，以满足边界条件。
?避免陷阱
TnTnn(),，22 例5(求解。 ，，，，
解:猜Tnn()(),,
证:用数学归纳法证明。 Tncn(),
，，T(n),2cn2，n,cn，n,,(n) --错～～ ，，
22
错在那里:过早地使用了而陷入了陷阱应该在证明 ,()n
了才可用。从不可能得 Tncn(),Tncnn(),，
到因为对于任何c>0，我们都得不 Tncn(),
cn，n,cn 到.
?变量替换
方法: 经变量替换把一个递归方程变换为我们熟悉的方程.
，，T(n),2Tn，lgn 例6. 求解
m,,mm2 解:令，则, TTm222,，. mn,lgn,2,,，，,,
m,,mm,,,,m2SmS(),2，mSmT(),2 令则TS2,. 于是, . ,,,,,,，，,,,,22,,
m，，T2,,(mlgm). 显然,,即 Smmm()(lg),,
m 由于2=n, m=lgn, . T(n),,(lgn，lg(lgn))
2.4.2 Iteration方法
?方法:循环地展开递归方程，把递归方程转化为和式，
然后可使用求和技术解之。
nTnnT(),，3 例1. ，，，，4
nn,，，n33T ，，，，，，，，416
23
,,n,,,,nn ,，，n33，3T,,,,，，,,，，，，464,,16,,，，
n,,nn,，，n39，27T ，，,,，，，，46416，，
nn,,,,,,23i,,nn,, ,，，n33，3，，.....3T,,i23,,,,，，4,,，，4,,44，，，，
ni 令 ,1,4,n,i,logn4i4
nn,,,,,,logn234n ，，,n，3，3，3，.....，3T1,,，，，，23,,,,444，，，，,,
ilogn,431,,in ,3，,(n),n,n，,4n,O(n),,i,,344,,00,,ii1,4
?方法的关键:
? 达到边界条件时，展开需要的循环次数.
? 由循环递归过程而得到和式.
?注意:
? 在循环中间可能猜出解，此时应停止循环.
? floor和ceiling使问题复杂化，我们可以假设方程定义在
k或 一个量的幂，如则可以省略. n,4，，，，
2.4.3 Master method
n目的:求解型方程, 是常数， ab,,10,TnaT()(),，fn，，b
24
是正函数 fn()
方法:记住三种情况，则不用笔纸即可求解上述方程.
1. Master 定理
定理2.4.1 设是常数，是一个函数, 是定义在fn()a,1和b,1Tn()
n非负整数集上的函数. 可以如下求解: Tn()TnaT()(),，fn，，b
aloga,,logbb，，f(n),,n,,0 ?. 若,是常数，则. Tnn(),,，，
logalogabb，，，，T(n),,nlgnf(n),,n ?. 若，则.
loga，,b，，f(n),,n,,0?. 若,是常数, 且对于所有充分大的n
n , c>1是常数, 则. Tnfn()(()),,af,cfn()，，b
logabn*直观地:我们用与比较 fn()
logalogabb若大，则 ?. nTnn(),,，，
?. 若大，则 fn()Tnfn()(()),,
logalogabb，，T(n),,nlgn,,(f(n)lgn)n ?. 若与同阶，则. fn()
*更进一步:
logabn?. 在第一种情况,不仅小于，必须多项式地小 fn()
logabnfnO,,0(),(). 于,即对于一个常数， ,n
logab?. 在第三种情况,fn()不仅大于，必须多项式地大 n
loga,b,,0f(n),,(n,n) 于，即对一个常数，.
25
*注意:这三种情况并没有cover 所有可能的 fn()
logab ? 情况1与情况2之间有空隙,即小于n,但不是多 fn()
项式也小于.
? 情况2与情况3也同样有间断空隙.
对于这两种情况，Master定理也无能为力.
2. Muster定理的使用
n 例1.求解. TnT(),，9n，，3
2logab,,n 解:abfnn,,,93，，(), n，，
log,,ab,,1 , ？fnnn(),,,，，
loga2b ？,,Tnnn(),,，，，，
2n 例2. 求解. TnT(),，1，，3
logalog10b3/23 解:, n,n,n,1abfn,,,1，，，()1，，2
loglogaabb , fnn()(),,,11,,Tnnnn()lg(lg),,,,，，，，
n 例3. 求解 TnT()lg,，3nn，，4
aloglog30.793b4，，a,3，b,4，f(n),nlgn，n,n,,n 解:
loga，,bf(n),nlgn,n,n,,02. ? ,
3nn3n3n ? 对所有n,，，,. af,3，lg,nlg,nlgn,cf(n)c,b444444
Tnfnnn()(())(lg),,,, 于是,
26
n 例4. 求解. TnT()lg,，2nn，，2
logalogabbabfnnn,,,22，，，()lg解:.大于nn,，但 fnnn()lg,n,n
不是多项式也大于, Master定理不使用于该. Tn()
2. Muster定理的证明
k ?当，k是正整数 n,b
k 引理1:设a,1, b>1, n=b, k是正整数， 则方程
(1)ifn,1,, T(n),,ifn,baT(n/b)，f(n),
的解为:
logn,1blogajjb T(n),,(n)，af(n/b),j,0
证明: T(n),f(n)，aT(n/b)
22,f(n)，af(n/b)，aT(n/b)
2233,f(n)，af(n/b)，af(n/b)，aT(n/b)，...
logn,1logn,1lognlognbbbb，af(n/b)，aT(n/b)
lognlognlognlognlognlogabbbbbbaT(n/b)aT(1),,(n) 由于, =. 于是 a,n
logn,1blogajjbT(n),(n)af(n/b),，. ,j,0
logn,1bkjj 引理2: 设a,1, b>1, n=b, k是正整数， 则 g(n),af(n/b),,j,0
loga,,logabbf(n),O(n)g(n),O(n)(1) if for , 则 ,,0
27
logalogabbf(n),,(n)g(n),,(nlgn)(2) if , then
(3) if for some 01, n=b, k为正整数, 则
n,1(1)if,, T(n),,kifn,baT(n/b)，f(n),
的解为:
loga,,logabbf(n),O(n)T(n),,(n) (1) if for some , then ,,0
logalogabbf(n),,(n)T(n),,(nlgn) (2) if , then
loga，,bf(n),,(n) (3) if for some , and if ,,0
for some 01
?使用循环展开法求解T(n)=,(n)。 logn
3.3 Quick-Sort算法
1(快速排序算法描述
?快速排序算法也是分治算法。
?把数组A[p...r]中的元素排序的分治三步骤:
36
?划分: 划分A[p...r]为两个非空子数组A[p...q]和A[q+1...r],
使得A[p...q]中的每个元素都小于等于A[q+1...r]中的
每个元素,其中的下标q是由划分算法确定的。
?分治: 递归地调用快速排序算法排序数组A[p...q]和A[p+1...r]。
?综合: A[p...q]和A[p+1...r]已经排序，这一步不需要任何操作。
?快速排序算法 QUICKSORT
QUICKSORT(A,p,r)
1 If p,(n)，我们有
22 T(n),cn-2c(n-1)+,(n),cn。
?平均时间复杂性分析
?几点说明:
? 设数组A中存储的n个数完全不同。
? RANDOMIZED-PARTITION的第3行调用PARTITION时，
A[p]已经与A[p…r]中的一个随机元素相互交换了。
? PARTITION返回的值，仅依靠于x=A[p]在数组A[p..r]
中的阶rank(x)，即小于等于x=A[p]的元素个数。
? 对于i=1,2,...n，交换A[p]与A[p..r]中一个随机元素
致使rank(x)=i的概率为1/n
?PARTITION算法产生各种划分的概率
? PARTITION的关键步骤:
4 While TRUE Do
5 Repeat j=j-1 Until A[j],x;
43
6 Repeat i=i+1 Until A[i],x;
7 If ip. 在算法
的第一次循环中,i将停止在p,j在p之前停止,A[p]与
A[q]被交换,A[p]被置于高区中. 算法结束时,低区有
rank(x)-1个数据,而且每个都严格小于x. 于是,对于
rank(x),2,数组A被划分为两部分,低区可能具有1、
2、…、n-1个数据，而且每种情况出现的概率为1/n.
命题2. 设n=r-p+1。PARTITION算法划分A的分布如下:
低区数据数 高区数据数 概率
1 n-1 2/n
2 n-2 1/n
3 n-4 1/n
……
n-2 2 1/n
44
n-1 1 1/n
?平均情况下的递归方程为
n,11[(T(1)+T(n-1))+]+,(n) T(n)=(T(q)，T(n,q)),nq,1
?求解递归方程T(N)
2(1) T(1)=,(1). 从最坏情况的分析知T(n-1)=,(n)。于是
112 (T(1)+T(n-1))=(,(1)+,(n)=,(n)。 nn
n,11(T(q)，T(n,q))+,(n)+,(n) (2) T(n)=,nq,1
n,12Tkn()()，, = ,nk,1
n,12Tkn()()，, (3) 解递归方程T(n)= ,nk,1
假设，a,b>0使得T(k), aklgk+b成立(k,n-1)，则可
n,12Tkn()()，, 以通过替代得到T(n)= ,nk,1
n,12(aklgk，b)，,(n) , ,nk,1
n,12a2bklgk，(n,1)，,(n) =。 ,nnk,1
n,11122klgk 下面我们将先证明,nlgn-n 。 ,28k,1
n/2,1n,1，，n,1klgkklgk =+ klgk,,,k,n2，，k,1k,1
45
n/21,n,1，，
,(lg-1)+lg nnkk,,k,1kn,2，，
n/21,n,1，，
k =lgn- k,,k,1k,1
11nn ,n(n-1)lgn-() ,12222
11n122 =nlgn-n+(nlogn) ,2842
1122 ,nlgn-n(当n,2) 28
2a112b22 于是，T(n),(nlogn-n)+(n-1)+,(n) 28nn
a ,anlogn+n+2b+,(n) 4
a =anlogn+b+(,(n)+b-n) 4
a 选择a充分大使得n大于,(n)+b，我们有 4
T(n),anlogn+b,
即，T(n)=O(nlogn).
3.4 Heap-Sort算法
1(堆的定义
定义1. 堆是一个满足下列条件的键码序列:k,k12ni2i
n,,且k,k (i=1,2,…)。 i2i+1,,2，，
*堆实际上可以看作是一棵完全二叉树。堆的特性可以解释为:完
全二叉树中任一结点的键值都大于或等于它的两个子女的键值。例如
46
<16,14,10,8,7,9,3,2,4,1>等价于如下的树:
*堆排序的基本思想:对一组待排序的键码，首先按堆的定义排成一个序列(称为建堆)，然后将最大的元素取出，用剩下的键码再建堆，得到次最大的关键码，如此反复进行，直到全部关键码都排好序为止。
*本节其余部分我们研究三个过程:
HEAPIFY:保持堆的性质，使一个树保持为堆。
BUILD-HEAP:由无序数组建立一个堆。
HEAPSORT:排序一个数组。
2(HEAPIFY过程
?算法定义
输入:数组A和下标i，在A对应的树中,以
LEFT(i)和RIGHT(i)为根的子树是堆.
输出: 修改的数组A,使得在A对应的树中,
47
以i为根的子树是堆.
HEAPIFY (A,i)
1 ,LEFT(i) ,
2 r,RIGHT(i)
3 IF ,heap-size[A] and A[]>A[i] ,,
4 THEN largest, ,
5 ELSE largest,i
, 6 IF ,heap-size[A] and A[r]>A[largest]
7 THEN largest, ,
8 IF largest,i
9 THEN exchange A[i],, A[largest]
HEAPIFY(A,largest)
* HEAPIFY把A[i]下降到堆中的适当位置,使以i为根的子树是一
个堆.
?例: 输入A=<16,4,10,14,7,9,3,2,8,1>, i=2.
?时间复杂性分析
? 在{A[i],A[LEFT(i)],A[RIGHT(i)]}中选出最大者所需时
48
间是,(1).
? 对以结点i为根的某个子树施行HEAPIFY所需的时间。
命题1.以结点i的子女为根的子树最多有2n/3个结点。最
坏情形发生在最低一层恰好为半满的情况。
证明.设以i 为根的完全二叉树高为h，则在最坏情形下以
结点i为根的完全二叉树中结点个数
h322*,hhn=(2-1)+2/2= 2
h而此时，左子树中的结点个数为2-1 (左子树有h-1层)
hhh,,22322322,,323,,h,,?=,=2-1 n33332
2?结点i的子树中的结点个数最多为n. 3
因此，HEAPIFY的运行时间可用下述递归的形式描述:
2 T(n),T(n)+,(1) 3
而根据marter理论中的第二种情形
2 若T(n)=T(n)+,(1) 3
2 则T(n)=,(nlog,lgn)= ,(lgn) 3
?HEAPIFY的运行时间为O(lgn)。
(一) 初始建堆
BULD-HEAP(A)
1. heap-size[A],length[A]
49
2. For i,，length[A]/2， downto 1
3. Do HEAPIFY(A,i)
复杂性分析:
每次调用HEAPIFY需要O(lgn)时间，而这种调用的次数为O(n),所以此算法的运行时间为O(n,logn)。(这是一个上界，尽管没错，但不够精确。)
下面要给出的一种较精确的分析依赖于下述性质:
h+1具有n个元素的堆，至多有，n/2，个高为h的结点(这是一个书中习题) 证明:设树高为k,用归纳法证明。
k 当h=0时，若最低是满的，则h=0的结点数为2(即第k层结点
h+1数)，且n=2-1。
k，1，，n121,，，，，kk2,而===，?此时命题成立。 2,,h，1,,,,222,,,,,,
k若最低层不满，我们不妨设h=0的结点数为, (1,,<2)
k,1k，1，，，，n,,2,,21,,，，，，，此时，==,=, ，,,,,h，1,,,,222222,,,,,,,,
?此时命题也成立。
k，，21,，,，，k-m,,假设h=m时命题成立，即,2(高为m的结点数即层 m，12,,,,
数为h-m的结点数)
50
k (设,是最低层结点数，即第k层结点数，1,,,2则当h=m+1时 ，n/ab，=，，n/a，/b，
kkk，，，，，，，，n21,，,21,，,21,，,1 k-mk-m-1 ，，===2,，2/2，=2,,,,,,,,,h，1m，1m，2m，2,,22222,,,,,,,,,,而我们知道高为(m+1)的结点处于(k-(m+1))层，？高为
k-(m+1)k-m-1 (m+1)的结点数最多为2= 2 ？此时的命题也成立。
在前面我们已知对高为h的结点调用HEAPIFY所需要的时间为0
(h)。
？我们可以将BUILD-HEAP所花的总的时间表示为:
nloglgn，，，，,,hn，，,,;n,= (n个结点的完全二叉树高为，lgn， ;(),h,,h，1h，1,,22,,,,h,0h,0
,xkkx,<1时，= 而我们知道:当,x,2,()1xk,0
,h12？==2 这里x=1/2,k=h) ,h22,k,0112，，
lgn,，，,,h,,h,,;n,？ BUILD-HEAP的运算时间为:==0(n) ;n,,,,,hh2,,2,,h,0,0h(二) 堆排序算法
HEAPSORT (A)
1. BUILD-HEAP(A)
2. FOR i,lenght[A] downto 2
3. Do exchange A[1]?A[i]
51
4. heap-size[A] , heap-size[A]-1
5. HEAPIFY(A,1)
复杂性分析
?调用BUILD-HEAP(A)所需的时间为0(n)而在(n-1)次循环中，每次调用HEAPIFY所需的时间为0(lgn)
?HEAPSORT算法的运行时间为0(nlgn)。
3.5 排序算法的时间复杂性下界
在这一部分我们将主要分析堆排序和快速排序算法。象归并排序，插入排序，堆排序，快速排序都是通过比较;来排序的算法。我们首先证明:任一用比较来排序的算法，当输入为n时，最坏情况下的比较次数f(n)=,(nlgn)。
为了证明它，我们首先看一下判定树的概念。
下面给出将三个数a,b,c排序的一棵判定树
A0和充分大的n，用比较进行排序的任一算法，在最坏情况下，至少需c,n,logn次比较才能把n个元素排序。即在最坏情况下的比较次数f(n)=,(nlogn)
证明:对于n,4
n
2nn，，,, ?n!,n(n-1)(n-2)...(), ,,,,,,22,,
n
2nnnnnn,, ?lgn!,lg=lg=(lgn-lg2)= lgn- ,,,,222222
nnnn =lgn+(lgn-),lgn 4424
我们已经知道将n个元素排序，最坏情况下的比较次数至少为判定树高，又根据定理1知，把n个不同元素排序的任一判定树高至少为logn! ?推论成立。
54
3.6 顺序统计量
在具有n个元素的集合中，第i个顺序统计量就是第i小的元素。例如:最小的元素是第一个顺序统计量，“大.....n.......” 这一节我们要讨论的问题是:从n个不同元素的集合中选出第i个顺序统计量。
这个选择问题可以形式化地描述如下:
输入:一个n个(不同)元素的集合A，及一个整数i (1,i,n) 输出:A中的元素x,它恰好大于A中的其它i-1个元素。
当然，我们可以先用堆排序或归并排序方法将集合A中的元素排序。那么其输出数组(集合用数组表示)中的第i个元素就是集合A中的第i个顺序统计量。因而我们可以在0(n,logn)时间内解决这个选择问题。然而，我们还可以有更好的算法。
?3.4.1 选出最小元素和最大元素
(一) 选出最小元素和最大元素
下面给出从n元素的集合中，选出最小元素的算法:
MINIMUM(A)
1. min,A[i]
55
2. for i,2 to length[A]
3. do if min>A[i]
4. then min,A[i]
5. return min
显然，执行此算法需要n-1次元素之间的比较。即运行时间为0(n)。同理，我们也可以在0(n)时间内选出最大元素。 (二) 同时选出最大元素和最小元素
在有些应用场合我们需要在具有n个元素的集合中同时找出最大元素和最小元素。
例如:要在屏幕上确定一个矩形区域时，要给出其左上角和右下角。
要设计一个在,(n)时间内从n个元素中同时找出最大元素和最小元素的算法并不难。比如，我们可以分别地找出最小元素和最大元素，这需要2(n-1)次元素之间的比较。
但，事实上，为了同时找出最小元素和最大元素，我们只要进行3，n/2，次元素之间的比较就够了。为此我们可以这样做:每次不是处理输入中的一个元素，而是处理一对元素。即，首先从输入中取出一对元素，让它们相互比较，然后令其中较小者与当前最小元素比较，令其中较大者与当前最大元素比较。这样，每两个元素需要比较3次。
56
?3.4.2 在线性的期望时间内进行选择
具有一般性的选择问题，看起来要比选出最小元素和最大元素困难多了。
但是，令我们惊奇的是，这两类问题具有同样的运行时间,(n)
下面我们将给出选择问题的一个分治算法。
RANDOMIZED-SELECT(A,P,r,i)
1. If p=r
2. Then return A[p]
3. q, RANDOMIZED-PARTITION(A,P,r)
4. k,q-p+1
5. If i,k
6. Then return RANDOMIZED-SELECT(A,P,r,i)
7. Else return RANDOMIZED-SELECT(A,q+1,r,i-k)
复杂性分析:
(1) 最坏情况:
?我们可能总是在剩余最多的子集中进行划分，那么我们需要调用0(n)次RANDOMIZED-PARTITION算法。而每调用一次最多需要0(n)时间。
57
2?此算法在最坏情况下的运行时间为0(n)。 (2) 平均情况:
我们可以用下述方法获得RANDOMIZED-SELECT算法的期望
运行时间T(n)的一个上界。
n,1
TT(n),1/n(max(1,n-1)+(max(k,n-k)))+0(n) ,k,1
n,1
,1/n(T(n-1)+2)+ 0(n) Tk(),kn,2，，
n,1
=2/n+ 0(n) Tk(),kn,2，，
从第一行得第二行的原因:
ifkkn,2,，，max(k,n-k)= ,ifnk,kn,2，，,
if n是奇数，则T(，n/2，)、T(，n/2，+1)、...T(n+1)各出
现两次
if n是偶数，则T(，n/2，)、T(，n/2，+2)、...T(n+1)各出
现两次而T(，n/2，)出现一次
总之，无论n是奇数还是偶数，第一行的和式总是小于等于第二行。
从第二行得第三行的原因:
2?在最坏情况下 T(n-1)=0(n)
?1/nT(n-1)能被0(n)吸收。
58
我们可用归纳法来求解上述递归方程:
假设 T(k),ck k,n-1,并将此假设代入上述递归方程得:
n21,n,1n,1，，2c2T(n),+0(n)= +0(n) (),ckkk,,,nnk,1k,1kn,2，，
2c=(1/2(n-1)n-1/2((，n/2，-1)，n/2，)+0(n) n
,c(n-1)-c/n(n/2-1),(n/2) +0(n)
=c(3/4,n-1/2) +0(n)
=cn-c(1/4,n+1/2) +0(n) ,cn (当c充分大时) ?任意一个顺序统计量，都可以在线性的平均时间内确定出来
?3.4.3 最坏情况下能在线性内进行选择的算法
下面我们给出一个理论意义上的选择算法，它最坏情况下的运行时间是0(n)。
从n个元素的数组中确定出第i子元素的选择算法SELECT执行如下步骤:
1. 将具有n个元素的输入数组分成，n/5，个具有5个元素的小组
和至多1个具有(n mod 5)个元素的小组。(若n不能被5
整除，则最后一个小组的元素个数即为n mod 5) 2. 用插入排序法分别将，n/5，个小组进行排序，并取出每组中的
中点元素(如果小组中具有偶数个元素，则取两个中点中较
59
大者。
3. 递归地调用SELECT找出，n/5，个中点元素中的中点元素x(即
对中点元素的集合递归地调用SELECT确定出地，，n/5，/2，小
的元素x
4. 用x调用修正的PARITION算法，将输入数组分割成两部分。
令k是分割出来的低部分的元素个数，则n-k是高部分的元
素个数。
5. 若i,k，则在低部分中递归地调用SELECT选出第i小元素，
若i>k，则在高部分中递归地调用SELECT选出第i小元素 例:, , , , ,
, , , , ,
, , , ,
中点集
,
, , , , ,
, , , , ,
分析:
?在第二步选出地所有中点元素中至少有一半是大于或等于中点元素中地中点元素x的。
?在，n/5，个小组中，至少有一半减两个小组包含3个大于x的元素(除去元素个数少于5的那一组和包含x自身的那一组外) ?在输入数组中大于x的元素个数至少是:
60
3(，1/2，n/5，，-2),3n/10-6,同理，在输入数组中小于x的元素个数至少也是3n/10-6
?在最坏情况下，在第5步至多对n-(3n/10-6)=7n/10-6个元素递归调用SELECT.
?现在我们能求算法SELECT在最坏情况下的运行时间T(n):
第1，2和4步花费0(n)时间。(第2步调用0(n)次插入
排序算法对元素个数为0(1)的集合进行排序)
第3步花费的时间为T(，n/5，)
注意:7n/10+620),此外对任意一个元素个数不大于80的输入，需要0(1)时间。
因此，我们可以获得如下的递归不等式:
,ifn,80,(10T(n), ,n,80ifTnTnn(()()571060，，，，，,
下面用归纳法证明运行时间是余割线性时间:
假设T(k),ck (k,n-1)
代入假设得:
T(n),c，n/5，+c(7n/10+6)+0(n),cn/5+c7n/10+6c+0(n)
=9cn/10+7c+0(n)=cn-c(n/10-7)+0(n),cn 可见，最坏情况下得运行时间是一个线性得时间。
第四章 Dynamic Programming技术
61
4.1 Dynamic Programming 概述
?优化问题: 一个优化问题可能有很多解，每个解有一
个代价，我们希望选择一个具有最少代价
的解。一个优化问题可能有多个优化解。
?动态规划方法:
?Dynamic Programming方法适用于:当一个优化问
题可分为多个子问题，子问题的解被重复使用。
?Dynamic Programming方法求解每个子问题仅一次，
并保存其结果，以后用到时直接存取，不重复计算，
——节省计算时间。
?Dynamic Programming方法自底向上，而divid-
and-conque方法自顶向下。
?动态规划算法的书记步骤
? 分析优化解的结构
? 递归地定义最优解的代价
? 自底向上地计算优化解的代价保存之，
并获取构造最优解的信息。
? 根据构造最优解的信息构造优化解
4.2. Matrix-chain Multiplication
62
4.2.1 问题的提出
?矩阵链乘法问题
输入: A是矩阵 12ni
输出:矩阵乘积 A，A，…，A12n
?矩阵链乘法的实现
?矩阵乘法满足结合率。
?计算一个矩阵链的乘法可有多种方法:
?例如:(A，A，A，A)=(A，(A，(A，A))) 12341234
=((A，A)，(A，A)) 1234
....
=((A，A)，A)，A) 1234
?两个矩阵的乘法A，B的代价依赖于计算的顺序
?复杂性测度:乘法的次数
?A，B的代价:设A是p，q矩阵，B是q，r矩阵，
则计算A，B的时间是0(pqr).
?矩阵链乘法的代价
设A=10，100矩阵, A=100，5矩阵, A=5，50矩阵, 则 123
?T((A，A)，A)=10，100，5+10，5，50=5000+2500=7500 123
?T((A，A) ，A)=100，5，50+10，100，50 123
=25000+50000=750000.
63
?结论: 不同解法有不同的代价。
?矩阵链乘法优化问题
输入:, A是p，p矩阵 12nii-1i
输出:代价最小的计算A，A，...，A的方法 12n
?矩阵链乘法优化问题的解空间
设p(n)=计算具有n个矩阵的矩阵链乘积的方法数
............AAAAn1kk+1n-kk
1 if n=1
p(n)=
n,1
pkpnk()(), if n,2 ,k,1
32(n,1)n,,12,, p(n)=C(n-1)=Catalan数== ,(4/n) ,,n,1n,,
*如此之大的解空间是无法用枚举方法求出最优解的～
4.2.2 优化解的结构
?几个记号
?A=A，A，....，A i-jii+1j
?cost(A)=计算A的代价 i-ji-j
?优化解的结构
?对于任意k,1,k 01n
?二维数组m[1..n,1..n],存储m[i,j]
?二维年数组s[1..n,1..n], 存储计算m[i,j]时确定的
优化解对应的k值.
?基本思想
?对于i,ki
THEN X=Matrix-Chain-Multiply(A,s,i,s[i,j]);
70
Y=Matrix-Chain-Multiply(A,s,s[i,j]+1,j);
Return Matrix-Multiply(X,Y);
Else Return Aj
4.3 动态规划原理
问题:什么情况下可以应用 Dynamic Programming 可用动态规划方法求解的问题必须满足:
1. 具有Optimal substructure
2. 具有Overlapping sub-problems
4.3.1 Optimal substructure
1(优化结构
定义1. 如果一个问题的优化解包含了他的子问题的优化解，
则称此问题具有优化结构。
*优化结构是应用动态规划方法的一个条件，也是应用Greedy
方法的一个条件，是否用动态规划方法，尚需看是否满足
Overlapping subproblems条件。
例1. Matrix-Chain-Multiply问题具有优化结构，因为
A，...，A的优化解(A，...，A) ， (A，...，A)包含 1n1nk+1n
71
子问题(A，...，A)和(A，…，A)的优化解。 1nk+1n
2.子问题空间
?理想情况:子问题空间越小越好，可减少时间和空间复杂性。
例1(? Matrix-Chain-Multiply问题的子问题是所有子链
的集合。
? 我们也可以使子空间为任意的矩阵子序例—太多
的无必要的子问题不得不被求解。
?合适子空间地确定
在分析问题的结构时，用循环方法可以得到一个好的子问题
空间。
例2((A，…，A)=(A，...，A)，(A，...，A) 1n1kk+1n1
=((A，...，A)，(A，...，A))， 1kk+1122
((A，...，A)，((A，...，A)) k+1kk+1n33
……
最后得到子问题空间为S={A，A，...，A,1,i,j,n}. ii+1j
我们来计算S的大小。S包括:
长为1的矩阵子链n个，
长为2的矩阵子链n-1个，……
长为n-1的矩阵子链2个，
72
长为n的矩阵子链1个.
于是，S的大小为n(n+1)/2。
4.3.2 Overlapping sub-problems
1.相交子问题
定义2.如果递归算法求解一个优化问题时，反复求解相同的
子问题，则称该优化问题有相交子问题。
*Dynamic Programming方法利用这种特点，只计算每个子问
题一次并保存，避免反复计算相同子问题多次。
*Divid-and-conguer方法每次都产生新问题并计算之，而不
管是否该子问题已计算过。
2(Matrix-Chain-Multiply的递归分解算法
?算法
Recursive-Matrix-chain(p,i,j)
If i=j Then Return 0;
M[i,j]=?;
For k=i To j-1 Do
q=Recursive-Matrix-chain(p,i,k)+
Recursive-Matrix-chain(p,k+1,j)+ppp i-1kj
If q. XYXYmnm-1n-1
? 若x,y，且z,x，则Z是X和Y的LCS，即 mnkmm-1
LCS=LCS XYXYm-1
? 若x=y,且z,y,则Z是X与Y的LCS，即 mnknn-1
76
LCS=LCS XYXYn-1
证明.
? 设z,x，则可加x=y到Z，得到一个长为k+1的X与Y的公共kmmn
序列，与Z是X和Y的LCS矛盾。于是z=x=y。 kmn
现在证明Z是X与Y的LCS。显然Z是X与Y的公共序列，k-1m-1n-1k-1m-1n-1
我们需要证明Z是LCS。设不然，则存在X与Y的公共子序列W，W的k-1
长大于k-1。增加x=y到W，我们得到一个长大于k的X与Y的公共序mn
列，与Z是LCS矛盾。于是，Z是X与Y的LCS。 k-1m-1n-1
? 由于z,x，Z是X与Y的公共子序列。我们来证Z是X与Ykmm-1m-1
的LCS。设X与Y有一个公共子序列W，W的长大于k, 则W也是X与m-1
Y 的公共子序列，与Z是LCS矛盾。
? 同?可证。证毕
*X和Y的LCS的优化解结构为
LCS+ if x=y XYmnmnm-1n-1
LCS= LCS if x,y,z,xXYXYmnkm m-1
LCSif x,y,z,y XY mnkn n-1
2.相交子问题 (见下边的递归图)
LCS XY
77
LCSLCS LCSXY XYXY m-1n-1m-1n-1
LCSLCSLCSLCSLCSLCS....... XY XY XY XY XYXY m-2n-2m-2n-1m-1n-2m-2n-1m-2 m-1n-1
*求LCS和LCS时都需要LCSXYXYXYm-1n-1m-1n-1
.......
3.子问题空间
?X与Y的LCS问题空间由求X与Y的前缀的LCS问题构成。
?由于X的前缀个数为m个，Y的前缀个数为n个，求X与Y
的前缀的LCS问题的个数为m*n个。于是子问题空间的大小
为,(m*n)。
4.4.3 建立求解LCS长度的递归方程
?定理1说明:
?If x=y, x属于X和Y的LCS，须求解X和Y的LCS。 mnmm-1n-1
?If x,y,必须求解须求解X和Y的LCS以及须求解X和Ymnm-1n-1
的LCS，长者是X和Y的LCS。
?令C[i,j]=X与Y的LCS的长度，则 ij
0 if i=0或j=0
C[i,j]= C[i-1,j-1]+1 if i,j>0 and x=yij
78
Max(C[i,j-1],C[i-1,j]) if i,j>0 and x,y ij
4.4.4 LCS长度的计算
1(基本思想
计算C[i,j]需先计算C[i-1,j-1]、C[i,j-1]、C[i-1,j]
C[i-1,j-1] C[i-1,j]
C[i,j-1] C[i,j]
先计算出第0行与第0列，然后逐行计算。
2(算法
?数据结构
C[0:m,0:n]: C[i,j]是X与Y的LCS的长度 ij
B[1:m,1:n]: B[i,j]是指针，指向计算C[i,j]时所选择的
子问题的优化解所对应的C表的表项。
?算法
LCS-length(x,y)
m,length(x);n,length(y);
For i,1 To m Do C[i,0],0;
For j,1 To n Do C[0,j],0;
For i,1 To m Do
For j,1 To n Do
If x=y ij
79
Then C[i,j],C[i-1,j-1]+1;B[i,j],“?”;
Else If C[i-1,j],C[i,j-1]
Then C[i,j],C[i-1,j]; B[i,j],“?”;
Else C[i,j],C[i,j-1]; B[i,j],“?”;
Return C and B.
4.4.5.构选优化解-LCS
1. 基本思想
从B[m,n]开始按指针搜索, 若B[i,j]=“?”，则x=y是LCS的一ij个元素。如此找到的“LCS”是X与Y的LCS的Inverse。
2(算法
Print-LCS(B,X,i,j)
IF i=0 or j=0 THEN Return;
IF B[i,j]=“?”THEN Print-LCS(B,X,i-1,j-1); Print x; i
ELSE If B[i,j]=“?”THEN Print-LCS(B,X,i-1,j);
ELSE Print-LCS(B,X,i,j-1).
*Print-LCS(B,X,length(X),length(Y))可打印出x与y的LCS。
例2.
j 0 1 2 3 4 5 6 7 I
B D C A B A
0 0 0 0 0 0 0 0
? ????1 A 0 00 0 1 ?1
80
1
???2 B 0 1 ??1 2 ?
1 1 2
?????3 C 0 1 1 2 ?2 2
2
?????4 B 0 1 1 2 2 3 ?
3
??????5 D 0 1 2 2 2 3 3
??????6 A 0 1 2 2 3 3 4
??????7 B 0 1 2 2 3 4 4
4.5 优化的多边形三角
4.5.1. 基本概念
多边形:一个多边形可以表示为顶点坐标的集合P=(v,v,...v)01n+1或顶点序列 vv,...vv。 01n-1n
定义1.一个多边形是简单的如果除了顶点以外没有任何边交叉点。
定义2.平面上由多边形封闭的点集合称为多边形的内部，多边形上的点集合称为多边形的边界，平面上除多边形内部和边界以外的点集合称为多边形的外部。
定义3.设P是一个多边形。若P的边界或内部的任意两点的连线上的所有点都在P的内部或边界上，则称P是凸多边形。
定义4.多边形P上的任意两个不相邻结点v、v所对应的 线ii+1
段vv称为弦。 ii+1
定义5.(三角剖分) 一个多边形P的三角剖分是将P划分为不相交
81
三角形的弦的集合。
定义6.(优化三角剖分问题) 设S是由多边形P的边和弦构成的三
角形集合，W是S上的代价函数。优化三角剖分问题定义为:
输入:多边形P和代价函数W
输出:求一个P的三角分T，使得w(t)最小，其中S是T T,t,sT
所对应的三角形集合。
4.5.2 优化三角分的结构分析
设P=(v,v,...v)是n+1点的多边形， 01n
T是X的优化三角剖分， x
则
vv0n
v1vk+1
vvk2
T=T(v, ..., v)?T(v, ..., v)?{vv,vv} P0kk+1n0kkn
4.5.3 优化三角剖分的代价函数
?代价函数
设t[i,j]=的优化三角剖分的代价，则: i-1,i,.....,j
t[i,i]=t[j,j]=0
82
t[i,j]= min{t[i,k]+t[k+1,j]+w(Δ)}. jkj-1vvv,,i-1kj
?算法
与矩阵链乘法问题一致，把Matrix-chain-Order和Matrix-
chain-Multiply 算法略加修改即可计算t[i,j]并构造优化
三角剖分解。
第五章 Greedy算法
5.1 Greedy算法的基本原理
1. Greedy算法
?Greedy算法的基本思想
?求解最优化问题的算法包含一些列步骤
?每一步都有一组选择
?作出在当前看来最好的选择
?希望通过作出局部优化选择达到全局优化选择。
*Greedy算法不一定总产生优化解。
*一个Greedy算法是否产生优化解，需要严格证明。
83
?Greedy算法产生优化解的条件
? Greedy-choice-property
? Optimal substructure
2. Greedy-choice-property(Greedy选择性)
定义1 若一个优化问题的全局优化解可以通过局部优化选择得到，则该问题称为具有Greedy选择性。
*Greedy算法与动态规划方法的不同
动态规划:每一步作一个选择 — 依赖于子问题的解。
Greedy方法: 每一步作一个选择 — 不依赖于子问题的解。
*一个问题是否具有Greedy选择性需要证明。
3.优化子结构
定义2 若一个优化问题的优化解包括它的子问题的优化解，则称其具有优化子结构。
4.与动态规划方法的比较
84
?动态规划方法可用的条件
? 优化子结构
? 子问题相交性
? 子问题空间小
?Greedy方法可用的条件
? 优化子结构
? Greedy选择性
*可用Greedy方法时，动态规划方法可能不适用。
*可用动态规划方法时，Greedy方法可能不适用。
5(Greedy算法正确性证明方法
? 证明算法所求解的问题具有优化子结构;
? 证明算法所求解的问题具有Greedy选择性;
? 算法按照?中的Greedy选择性进行局部优化选择。
5.2 调度问题
85
1( 问题的定义
?活动:设S={1,2,…,n}是n个活动的集合，每个活动使用一个
资源，每个资源只能为一个活动使用。 ?起始终止[sf]时间: 每个活动i有一个起始时间s，一个终 i，ii
止时间f，s, fiii ?相容活动:活动i和j是相容的，若s,f或s,f，即 jiij
fSSifijj时间
或
SfSfjjii时间
?调度问题:
输入:S={1,2,…,n}，F={[sf]}，n,i,1 i，i
输出:S的最大相容集合
2. 调度算法
?基本思想
86
为了选择最多的相容活动，每次选f最小的活动， i
即使以后可选更多的活动——“贪心”。 ?算法
设f,f,….,f已排序 12n
Greedy-Activity-Selector(S,F)
n,lenyth(s);
A,{1}
j,1
FOR i,2 To n Do
IF s,f ij
THEN A,A?{i};j,i;
Return A.
?复杂性分析
IF 结束时间已排序 T(n)=,(n)
IF 结束时间未排序 T(n)=,(n)+,(nlogn)=,(nlogn)
?算法正确性
注意:要证明调度算法产生优化解，我们需要证明:
87
? 调度问题具有Greedy选择性。
? 调度问题具有优化子结构。
引理1 设S={1,2,…,n}是n个活动集合，[sf]是活动的起始终i，i
止时间，且f,f,….,f，S的调度问题的某个优化解包括活动1。 12n
证.设A是一个优化解，按结束时间排序A中活动，设其第一个活动为k。
如果k=1，引理成立。
如果k,1，令B=A-{k}?{1},由于f,fB中活动相容。又由于,B,=,A,, 1k,
所以B是一个优化解，且包括活动1.
引理2(优化子结构) 设S={1,2,…,n}是n个活动集合，[sf]i，i是活动i的起始终止时间，且f,f,….,f，设A是S的调度问题的一12n
个优化解且包括活动1，则A,=A-{1}是S,={i,s|s,f}的调度问题的优i1
化解。
证. 显然，A,中的活动是相容的。我们仅需要证明A,是最大的。设不然，存在一个S’ 的调度问题的优化解B,，,B,,>,A,,。令B={1}?B,。对于,i,S,,s,f,B中活动相容。由于|A’|=|A|-1, ,B,=,B,,+1>,A,,+1=,A,，与i1
A最大矛盾。
引理3(Greedy选择性)设S={1,2,….,n}是n个活动集合，f=0,l0i是S={j,S | s,f}中具有最小结束时间f的活动l。设A是S的包iji-1lii
88
k
{}l含活动1的优化解，其中，f,….,f，则A=。 1n:ii,1
证.对,A,作归纳法.当,A,=1时，由引理1，命题成立。设,A,,k时，命题成立。当,A,=k时,由引理2，A={1}?A, A是S={j,S|s,f}的优化112j1
kk{}l{l}解，由归纳假设，A=.于是,A=。 1::iii,1i,2
定理1. Greedy-Activity-Selector算法能够产生最优解。
证. Greedy-Activity-Selector算法按照引理3的Greedy选择性进行局部优化选择。
5.3 Huffman codes
5.3.1. 问题定义
1. 二进制字符编码:每个字符用一个二进制0、1串来表示。
2. 固定长编码: 每个字符都用相同长的0、1串表示。
3. 可变长编码: 经常出现的字符用短码，不经常出现的用长码。
4. 前缀编码:无任何字符的编码是另一个字符编码的前缀
5(编码树:
?叶结点:用字符及其出现频率标记。
?内结点(包括根结点):其子树的叶子的频率和。
89
?边标记:一个结点的左侧边标记0，右侧边标记1。
例:
100 0 1
a:45
55 0 1
25 30
1 0 1 0
c:12 b:13 14 d:16
1
0
f:15 e:9
*每个字符的编码=从根到对应的叶路径上的0、1串。
90
6. 编码树T的代价
设C是字母表,,c,C,
f(c)是c在文件中出现的频率
d(c)是叶子c在树T中的深度，即c的编码长度, T
T的代价是编码一个文件的所有字符的代码位数:
fcdc()() B(T)=。 ,T,cC
7.优化编码树问题
输入:字母表C={c,c,....,c}， 12n
频率表F={f(c),f(c),...,f(c)} 12n
输出:具有最小B(T)的C前缀编码树。
5.3.2 Huffman算法——产生优化前缀编码树
1(基本思想
循环地选择具有最低频率的两个结点，生成一棵子树，直至形成树。
例:初始: f:5 e:9 c:12 b:13 d:16 a:45
91
c:12b:13a:4525d:16a:4514第二步:14d:16第一步:010110
c:12f:5e:9f:5e:9b:13
25第三步:第四步:a:4530a:45550101
25c:12b:133001d:16141010c:12b:13
d:16f:5e:914
10
f:5e:9100第五步:10
55a:4501
25300110c:12b:13
d:1614
10
f:5e:9
2(算法
Huffman(C，F)
1. n,,C,;
2. Q,C;
3. FOR i,1 To n-1 Do
4. z,Allocate-Node( ); 5. x,left[z],Extract-MIN(Q); 6. y,right[E],Extract-MIN(Q); 7. f(z),f(x)+f(y);
8. insert(Q,z);
92
9. Return Extract-MIN(Q).
3. 复杂性分析
?设Q由一个堆实现
?第2步使用堆排序的BUILD-HEAP实现，要求时间O(n)
?每个堆操作要求O(logn)，循环n-1次，要求:O(nlgn)
?T(n) = 0(n) + 0(nlogn)。
4(Huffman算法的正确性
我们需要证明:
? 优化前缀树问题具有优化子结构;
? 优化前缀树问题具有Greedy选择性;
? 算法按照?中的Greedy选择性进行局部优化选择。
引理1(Greedy选择性). 设C是字母表，,c,C，c具有频率f(c), x、y是C中具有最少频率的两个字符，则存在一个C的优化前缀树，x与y的编码具有相同长度，且仅在最末一位不同。
证:设T是一个C的优化前缀树，且b和c是具有最大深度的两个
93
字符:
T
x
y
b c
不失一般性，设f(b),f(c),f(x),f(y). 因x与y是具有最低频率的
字符, f(b),f(x), f(c),f(y)。
从T构造T,:交换T的b和x:
T,
b
y
x c
94
从T,构造T,,:交换T的y和c:
T,,
b
c
x y
往证T,,是最大前缀树.
fcdcfcdc()()()(), B(T)-B(T,)= ,,TT'cC,,cC
=f(x)d(x)+f(b)d(b)-f(x)d(x)- f(b)d(b) TTTT’’
=f(x)d(x)+f(b)d(b)-f(x)d(b)- f(b)d(x) TTTT
=(f(b)-f(x))(d(b)-d(x)). TT
?f(b),f(x),d(b),d(x) (因为b的深度最大) TT
?B(T)-B(T’),0, B(T),B(T’)
同理可证B(T’),B(T’’). 于是B(T),B(T’’).由于T是最优化的，所
95
以B(T),B(T’’). 于是,B(T)=B(T’’)，所以T’’是C的最优化前缀编码树. 在T’’中, x和y具有相同长度编码, 而且仅最后一位不同。
引理2(优化子结构).设T是字母表C的优化前缀树，,c,C，f(c)是c在文件中出现的频率。设x、y是T中任意两个相邻叶结点，z是它们的父结点，则z作为频率为f(z)=f(x)+f(y)的字符，T’=T-{x,y}表示了字母表C’=C-{x,y}?{z}的优化前缀编码树。
证.
,c,C-{x,y}, d(c)=d(c)。于是f(c)d(c)=f(c)d(c)。 TTTT’’
由于d(x)=d(y)=d(z)+1， TTT’
f(x)d(x)+f(y)d(y)=(f(x)+f(y))(d(z)+1) TTT’
=(f(x)+f(y))d(z)+(f(x)+f(y)) T’
由于f(x)+f(y)=f(z),
f(x)d(x)+f(y)d(y)=f(z)d(z)+(f(x)+f(y)).于是 TTT’
B(T)=B(T’)+f(x)+f(y).
若T’是C’的非优化前缀编码树，则必存在T’’，其叶子在C’中，使
B(T’’),B,，由图论定GGG
理可知，具有k条边的森林包括,V,-k棵树，于是，A包括,V,-,A,棵树，B包括,V,-,B,棵树。
由于B具有较少的树，B一定包含一个树T，T的结点在A的不相同树中。T是连通的，必包括一条边(u, v)，使得u和v在A的不相同树中。(u, v),A-B连接A的两棵不同的树，(u, v)可以加到A，(V, A,{(u,v)})是森林，A,{(u,v)}, I，于是M满足交换性。 GG
3. Matroid的性质
定义2. 设M=(S，I)是一个Matroid，A,I。x,A称为A的一个
99
extension如果A,{x},I。
定义3. 设M=(S，I)是一个Matroid，A,I(A称为M的独立子集合)。如果A没有extension，则称A为最大独立子集合。
定理2. 一个Matroid的所有最大独立子集合都具有相同大小。
证. A是Matroid M的最大独立子集合，而且存在M的另一个独立子集合B, ,A,<,B,。根据M的交换性，，x,B-A使得A,{x},I，与A最大矛盾。
定义4(加权Matroid)设M=(S，I)是一个Matroid。如果存在一个权函数W，使得,x,S, W(x)是一个正数，则称M是加权Matroid。
*权函数W可以扩展到S的任意子集合A:w(A)=. W(x),
x,A
5.4.2 加权Matroid上的Greedy算法
定义1. Matroid M=(S，I)中具有最大权值W(A)的独立子集A,I称为M的优化子集。
1. 背景
?很多可用Greedy算法获得最优解的问题可以归结为在加权Matroid中寻找优化子集的问题，即给定M=(S，I)和权函数W，找到一
100
个独立子集A,I，W(A)最大。
?例子 — 最小生成树问题
?问题定义
输入:无向图G=(V，E)，权函数W: E,正整数。
输出:边子集合A,E满足
A中边联接所有V中结点。
W(A)最小。
?最小生成树问题转换为加权Matroid上寻找优化子集问题
构造:
? M=(S，I)是5.4.1中的图Matroid， GGG
? W’(e)= W-W(e)，W>max{w(e)}， 00
显然，,e,E，w’(e)>0，W’扩展为
W’(A)=(,V,-1) W-W(A)，,A,E 0
显然，M的最优子集A满足: G
A中边联接所有V中结点
W’(A)最大，即W(A)最小.
?于是，最小生成树问题可以由求M的最优子集的算法来求解。 G
2(加权Matroid中的优化子集寻找问题的定义
101
输入:Matroid M=(S,I), M的加权函数W
输出:M的最优子集
3(算法
Greedy(M,W)
1 A=,;
2 按权w值大小排序S;
3 FOR ,x,S(按w(x)非增序)DO
4 If A,{x},I /*每次选择具有最大w(x)的x — 贪心*/
5 Then A,{x};
6 Return A.
4. 时间复杂性
step 2: O(,s,log,s,)
step 4: O(f(,s,))
T(,s,) = O(,s,lg,s,+,s, f(,s,)
5. 正确性
102
引理1 Greedy算法总是返回一个独立子集合.
证.
设Greedy返回集合A，对,A,做数学归纳法.
当,A,=0时，A是空集合，由Matroid定义，A是独立子集合.
设,A,,k时，A是独立子集合。当,A,=k+1时，A由算法第4—5步得到，即A= A,{x}。由第4步已判定A,{x},I，所以A=A,{x}是独立子集合。
*我们需要证明A是最优子集，即证明:
加权Matroid最优子集问题具有Greedy选择性。
加权Matroid最优子集问题具有优化子结构。
Greedy算法按照上述优化子结构和选择规则选择最优子集合。
引理2(Greedy—选择性) 设M=(S, I)是一个加权Matroid，W是M的权函数，S按照W的值被排序(非递增)。如果S的第一个元素x使得{x},I，则存在一个M的优化子集A，x,A。
证.
如果S的第一个元素x不满足{x},I，则独立子集只能是空集，引理得证。
103
如果S的第一个元素x满足{x},I，若存在优化子集A包含x，则引理得证。若不然，设B是任意非空优化子集，x,B。显然,y,B，w(x),w(y)，如下构造包含x的优化子集A:
初始A={x},I;
利用交换性，对,y,B-A，若A,{y},I, A=A,{y}，直至,A,=,B,。
显然，A=(B-{y}),{x} for some y,B。于是
W(A)=W(B)-W(y)+W(x),W(B)，
因为B是优化子集，所以A也是优化子集，且x,A，明所欲证。
引理3. 设M= (S, I)是Matroid。如果x,S不是空集,的extension,则x不是任何独立子集合的extension。
证. 设x,S是A的extension但不是,的 extension。由于x是A的extension，A,{x},I。 由M的遗传性，{x},I，即{x}是,的 extension，矛盾。
*任何元素一旦不能被选中，则永远不会被选中。
*Greedy算法不会由于不再考虑未被初始选中的元素而产生错误。
104
引理4 (优化子结构) 设x是第一个被Greedy算法选中的元素。寻找包含x的优化子集问题可归结为找出M’=(S’, I’)的优化子集的问题，M’=(S’, I’)定义如下:
S’={y,S,{x,y},I}，
I’={B,S-{x} , B,{x},I}
而且M’的权函数与M的权函数相同。
证. 如果A是M的优化子集且x,A，则A’=A-{x},I’。反之，如果A’,I’, A=A’,{x},I。由于W(A)=W(A’)+W(x)，由M包含x的优化子集A可以得到M’的优化子集A’，反之亦然。
定理1 (Greedy正确性) 设M=(S, I)是一个Matroid，W是M的权函数，则Greedy(M,W)返回一个M的优化子集。
证.
(1) 引理3说明，任何没有被Greedy选中的S的元素，以后不会被选中，可以不再考虑。
(2) 一旦S的第一个x被选中，x可以加到A，因为引理2说明存在一个包含x的优化子集。
(3) 引理4意味着余下的问题是在M’中求解最优子集的问题。
Greedy算法是按照上述三个规则工作的，所以，则Greedy(M,W)
105
返回一个M的优化子集。
5.5 任务调度问题
1. 问题的定义
?单位时间任务:需要一个单位运行时间的任务。
?单位时间任务的调度问题:
输入:单位时间任务集合S={1,2,…, n}，
正整数任务期限集合D={d,d,…,d}, 任务i必须在d前完成， 12ni
非负权集合W={w,w,…,w}，任务i不在d前完成罚款w。 12nii
输出:S的一个调度(即S的一个执行顺序)，最小化总的罚款。
?任务调度问题转换为寻找加权Matroid的优化子集问题
定义1.给定一个任务调度。我们称一个任务在该调度中是迟的如果它在规定的期限之后完成;否则，这个任务在该调度中是早的。
106
任务调度的规范化:
(1). 一个调度可以如下安排成早任务优先形式(即早任务总是先于迟任务):如果早任务x跟在迟任务y之后，交换x和y的位置。
(2). 一个调度可以如下安排成规范形式(早任务总是先于迟任务，而且按期限的非降顺序执行任务):
第一步:将调度安排成早任务优先形式;
第二步:如果任务i和j是早任务，而且分别完成于时间k和k+1， d，lgn，，位A[i]始终不发生变化。
nlg,，，1n2 ?发生的位翻转的总次数为 ,,nn,,ii22,,00ii
?初始为零的计数器上的n次INCREMENT操作的最坏
情况时间为O(n)，每次操作的平摊代价为O(n)/n=O(1)。
6.2 会计方法
6.2.1 会计方法的原理
116
?首先定义每个操作的平摊代价然后计算总的平摊代价
?执行不同的操作需要付出不同的费用
?某些操作的费用可能比它们的实际代价多或少
?执行一个操作需要付出费用称为这个操作的平摊代价
?当一个操作的平摊代价超过了它的实际代价时，两者的差值
被作为存款赋给数据结构中一些特定的对象
?存款在以后用于补偿那些平摊代价低于其实际代价的操作
?一个操作的平摊代价可看作为两部分:其实际代价与存款
*会计方法不同于聚集方法，不同操作具有不同的平摊代价。
*在选择操作的平摊代价时要非常小心。如果我们希望通过对平摊代价的分析说明每次操作具有较小的最坏情况平均代价，则操作序列的总的平摊代价就必须是该序列的总的实际代价的一个上界。而且，像在聚集方法中一样，这种关系必须对所有的操作序列都成立。这样与该数据结构相联系的存款始终应该是非负的，因为它表示了总的平摊代价超过总的实际代价的部分。如果允许总的存款为负的的话(开始时对某些操作的费用记得过低)，则在某一时刻总的平摊代价就会低于总的实际代价。对到该时刻为止的操作序列来说，总的平摊代价就不会是总的实际代价的一个上界。所以，我们必须始终注意数据结构中的总存款不能是负的。
117
6.2.2 会计方法实例 1 — 栈操作
为了说明平摊分析中的会计方法，我们再回过头看看栈的例子。
1. 各栈操作的实际代价:
PUSH 1,
POP 1,
MULTIPOP min(k,s)
其中k为MULTIPOP的一个参数，s为调用该操作时栈的
大小。
2. 各栈操作的平摊代价:
PUSH 2,
POP 0,
MULTIPOP 0,
118
*MULTIPOP的平摊代价是个常数0，而它的实际代价却是
个变量。
3. 栈操作序列代价分析
?假设我们用1元钱来表示代价的单位
?开始时栈是空的。栈数据结构与在餐馆中一堆迭放的盘
子类似
?当将一个盘子压入堆上时，用,元来支付该压入动作的
实际代价，并有,元的存款(记的是,元的帐)，将该,元
钱放在刚压入的盘子的上面
?在任何一个时间点上，堆中每个盘子的上面都有,
元钱的余款
?盘中所存的钱是用来预付将盘从栈中弹出所需代价
?当执行一个POP操作时，对该操作不用收任何费，只要
用盘中所存放的余款来支付其实际代价即可
?为弹出一个盘子，拿掉该盘子上的,元余款，并用
它来支付弹出操作的实际代价
?这样，在对PUSH操作多收了一点费后，就无须对
POP操作收任何费
119
?MULTIPOP操作也无须收费
?为弹出第一个盘子，取出其中的,元余款并用它支
付一次POP操作的实际代价
?为弹出第二个盘子，再取出该盘上的,元余款来支
付第二次POP操作，等等
?这样，对任意的包含n次PUSH、POP和MULTIPOP操
作的序列，总的平摊代价就是其总的实际代价的一个上
界。又因为总的平摊代价为O(n)，故总的实际代价也为
O(n).
6.2.3 会计方法实例2 — 二进计数器的增值
为进一步说明会计方法，我们再来分析一下作用于一个初始为0的二进计数器上的INCREMENT操作。我们前面已经说过，这个操作的运行时间与发生翻转的位数是成正比的，而位数在本例中即为代价。我们还是用,元钱来表示单位代价(此例中即为某一位的翻转)。
?我们规定对将某一位置为,的操作收取,元的平摊费用。
?当某数位被置定1后，用,元中的,元来支付置位操作的实
际代价，而将另,元存在该位上作为余款。
?在任何时间点上，计数器中每个,上都有,元余款。
120
?将某位复位成,时不用付任何费，只要取出该位上的,元余
款即可。
?现在就可以来确定INCREMENT的平摊代价了:
?在while循环中复位操作的代价是由有关位上的余款来
支付的
?在INCREMENT第,行中至多有一位被复位，所以一次
INCREMENT操作的代价至多为,元
?对n次INCREMENT操作，总的平摊代价为O(n)
?因为计数器中为,的位数始终是非负的，余款量总是非
负的，总的实际代价上界为总的平摊代价，即O(n)。
6.3 势能方法
6.3.1 势能方法的原理
?势能方法不是将已预付的费用作为存储在数据结构特定对象
中的存款来表示，而是表示成一种“势能”，或“势”，它在
需要时可释放出来以支付后面操作的代价。
?势是与整个数据结构而不是其中的个别对象发生联系的。 ?势能方法的工作过程:
121
?设
?对一个初始数据结构D执行n个操作， 0
?对每个i=1,2,...,n，c为第i个操作的实际代价，D为 ii
对数据结构D执行第i个操作的结果。 i-1
?势函数,将每个数据结构D映射为一个实数,(D)，即与 ii
数据结构D相联系的势。 i
’’ ?第i个操作的平摊代价c定义为:c,c+ ,(D)-,(D) iii ii-1
*每个操作的平摊代价为其实际代价加上由于该操作所增加的势。
?n个操作的总的平摊代价为:
nnncDD，,,,()() , c',(c，,(D),,(D)),,,in0iiii,1,i1i,1i,1
n ?如果势函数,满足,(D),,(D)，则总的平摊代价就 c',n0ii,1
是总的实际代价的一个上界。
*在实践中，我们定义,(D)为0，然后再证明对所有i有,(D),0. 0i
?势能在平摊分析中的作用
’ ?如果第i个操作的势差,(D)-,(D)>0，则平摊代价cii-1I
就表示对第i个操作多收了费，同时数据结构的势也
随之增加了。
’ ?如果第i个操作的势差,(D)-,(D)>0，，则平摊代价cii-1I
122
表示对第i个操作的收费不足，这时就通过减少势来
支付该操作的实际代价。
*平摊代价依赖于所选择的势函数,。不同的势函数可能会
产生不同的平摊代价，但它们都是实际代价的上界。
6.3.2 势能方法实例1 — 栈操作
为了说明势能方法，我们再一次来研究一下栈操作PUSH、POP和MULTIPOP。
?势函数定义
?,(D)=栈D中对象的个数
?初始栈D为，,(D)=0 00
?因为栈中的对象数始终非负，第i个超作之后的栈D满 I
足,(D),0=,(D) i0
?以,表示的n个操作的平摊代价的总和就表示了实际代
价的一个上界。
?作用于包含s个对象的栈上的栈操作的平摊代价
?如果第i个操作是个PUSH操作
123
?实际代价:c=1 i
?势差:,(D) , ,(D)=(s+1) , s=1， ii-1
’ ?平摊代价:c=c+,(D),,(D)=1+1=2 i iii-1
?如果第i个操作是MULTIPOP(S, k)
且弹出了k’=min(k,s)个对象
?实际代价:c=k’ i
?势差:为,(D) , ,(D)= ,k’ ii-1
’ ?平摊代价:c=c+,(D),,(D)=k’ , k’=0 iiii-1
?如果第i个操作是POP
?实际代价:c=1 i
?势差:,(D) , ,(D)= ,1 ii-1
’ ?平摊代价:c=c+,(D),,(D)=1,1=0 iiii-1
?平摊分析
?每个栈操作的平摊代价都是O(1)
?n个操作序列的总平摊代价就是O(n)
?因为,(D),,(D)， n个操作的总平摊代价即为总的实 i0
际代价的一个上界，即n个操作的最坏情况代价为O(n).
6.3.3 势能方法实例2 — 二进计数器的增值
124
作为说明势能方法的另一个例子，我们再来看看二进计数器的增值问题。
?势函数定义
?,(D)=计数器D中1的个数
?计数器初始状态D中1的个数为0，,(D)=0 00
?因为栈中的对象数始终非负，第i个超作之后的栈D满 i
足,(D),0=,(D) i0
?以,表示的n个操作的平摊代价的总和就表示了实际代
价的一个上界。
?第i次INCREMENT操作的平摊代价
?设第i次INCREMENT操作对t个位进行了置0, i
至多将一位置1
?该操作的实际代价:c=O(t+1) ii
?在第i次操作后计数器中1的个数为b, b- t +1 ii-1i
?势差:,(D)-,(D),(b- t +1)-b=1- t ， ii-1i-1ii-1i
’ ?平摊代价:c= c+,(D)-,(D),( t +1)+(1- t )=2 i iii-1ii
?计数器初始状态为0时的平摊分析
125
?每个操作的平摊代价都是O(1)
?n个操作序列的总平摊代价就是O(n)
?因为,(D),,(D)，n个操作的总平摊代价即为总的实 i0
际代价的一个上界，即n个操作的最坏情况代价为O(n).
*势能方法给我们提供了一个简易方法去分析开始时不为零的计数器。开始时有b个1，在n次INCREMENT操作之后有b个1，0,b，0n0b,k。我们可将等式 n
nnncDD，,,,()(), c',(c，,(D),,(D)),,,in0iiii,1,i1i,1i,1
重写为
nn。 c,c',,(D)，,(D),,nii0i,1i,1
’对所有1,i,n，c , 2。因为,(D)=b，,(D)=b，n次INCREMENT操i00nn
作的总的实际代价为
nn
cbbnbb,,，,,，22. ,,00inn11i,,i
因为b,k，如果我们执行了至少n=,(k)次INCREMENT操作，则无论n
计数器中包含什么样的初始值，总的实际代价都是O(n)。
6.4 动态表
126
6.4.1 表的动态扩张和收缩问题
在有些应用中，开始时无法预知要在表中存储多少个对象。可以先为该表分配一定的空间，但后来很可能会觉得不够，这样就要重新为该表分配一个更大的空间，而表中的对象就要复制到新表中。类似地，如果有许多对象从表中删去了，就应该给原表分配一个更小的空间。这一节的目的是:
?研究表的动态扩张和收缩的问题。
?利用平摊分析证明插入和删除操作的平摊代价为O(1)，即
使当它们引起了表的扩张和收缩时具有较大的实际代价。
?如何保证一动态表中未用的空间始终不超过整个空间的一
部分。
?动态表支持的操作
?TABLE—INSERT:将某一元素插入表中
?TABLE—DELETE:将一个元素从表中去掉
?数据结构用一个数组或一组数组来实现动态表
?非空表T的装载因子,(T)=表存储的对象数,表大小
*空表大小为0，其装载因子为1
*如果动态表的装载因子以一个常数为下界，则表中未使用
的空间就始终不会超过整个空间的一个常数部分。
127
6.4.2 表的扩张
?向表中插入一个数组元素时，分配一个包含比原表更多的
槽的新表，再将原表中的各项复制到新表中去。 ?一种常用的启发式技术是分配一个比原表大一倍的新表，
如果只对表执行插入操作，则表的装载因子总是至少为
1/2，这样浪费掉的空间就始终不会超过表总空间的一半。 ?设T表示一个表
?table[T]是一个指向表示表的存储块的指针
?num[T]包含了表中的项数
?size[T]是T的大小，
?开始时，num[T]=size[T]=0。
?算法
TABLE—INSERT(T, x)
1 If size[T]=0
2 Then allocate table[T] with 1 slot;
3 size[T],1;
If num[T]=size[T] 4
5 Then allocate new table with 2，size[T] slots;
128
6 insert all items in table[T] into new-table;
7 free table[T];
8 table[T],new-table;
9 size[T],2，size[T];
10 Insert x into table[T];
11 num[T],num[T]+1.
?算法注释
?TABLE—INSERT过程本身称为复杂插入操作
?第10行中的插入称为基本插入操作
?每个基本插入操作的代价为1
?第5—9行中执行then语句的事件称为一次扩张
?第2行中分配初始表的开销为常数
?第5行与第7行中分配和释放存储的开销由第6行中转
移表中所有项的开销决定
?初始空表上的n次TABLE—INSERT操作的粗略分析
?第i次操作的代价
c=1, 如果当前的表中有空闲空间或i=1. i
c=i, 如果当前表是满的 i
129
(因为这时第10行中基本插入操作的代价为1，第6行原表复制到新
表的代价为i-1)
?如果执行了n次操作
?一次操作的最坏代价为O(n)
2 ?n次操作的总的运行时间的上界为O(n)
*这个界不精确，因为执行n次TABLE—INSERT操作的过程中并不常
常包括扩张表的代价。仅当i-1为2地整数幂时第i次操作才会引起一
次表地扩张。
*实际上，每一次操作地平摊代价为O(1)
?用聚集方法分析初始空表上的n次TABLE—INSERT操作
i,如果i,1为2的一个整数幂 ?第i次操作地代价为 c,,i否则1,
?n次TABLE—INSERT操作地总代价为
,,lgn,,n，，j c,n，2,n，2n,3n,,ii,1j,0
(因为至多有n次操作代价为1，余下操作的代价构成了一个几何级数)
?每一操作的平摊代价为3n/n=3。
?用采用会计分析初始空表上的n次TABLE—INSERT操作
?表中每一数据项的平摊代价为3元:
?将其自身插入当前表中的费用为一元
?当表扩张时其自身的移动的费用为一元
?为已经在表中的某个数据项存款一元
130
?注释
?刚完成扩张后表大小为m，表中有m/2项，且
没有“存款”。
?对每一次插入操作要收费3元:
?立即发生的基本插入的代价为1元
?另有1元放在刚插入的元素上作为存款
?余下的1元放在已在表中的m/2个项的某一项
上作为存款
?添满表需要m/2次插入
?到该表包含了m个项(已满)时，每一项都有1
元存款以支付在表扩张时引起的基本插入。
?总的平摊代价为3n=O(n).
?用势能方法分析初始空表上的n个TABLE—INSERT操作
?定义势函数,
?函数,必须满足
?完成扩张时:,(T)=0
?表满时:,(T)=size[T]
(下一次扩张的代价就可以由存储的势来支付了)
?,(T)的定义
131
,(T)=2,num[T]-size[T]。
?,(T)的性质
?完成一次扩张后，num[T]=size[T]/2，,(T)=0。
?表满时，num[T]=size[T]，,(T)=num[T]
?由于num[T],size[T]/2，,(T),0，n次TABLE—
INSERT操作的总的平摊代价就是总的实际代价
的一个上界。
?平摊分析
?符号
num=第i次操作后表中所存放的项数， i
size=第i次操作后表的大小， i
,=第i次操作后表的势 i
初始: num=size=,=0。 000
?第i次TABLE—INSERT操作的平摊代价
?如果未触发表扩张，则size= size，该操作的平摊 ii-1
代价为
’ c= c+,-,iiii-1
=1+(2,num-size)-(2,num-size) iii-1i-1
=1+(2, num-size)-(2,(num-1)-size) iiii
=3
132
?如果触发表扩张，则size/2=size=num-1，该操作 ii-1i
的平摊代价为
c’=c+,-,=num+(2,num-size) - (2,num-size) iiii-1iiii-1i-1
=num+(2,num-(2,num-2))-(2,(num-1) - ( num-1)) iiiii
=num+2-(num-1)=3 ii
?总的平摊代价为O(n).
6.4.3 表扩张和收缩
为了实现TABLE—DELETE操作，只要将指定的项从表中去掉即可。但是，当某一表的装载因子过小时，我们就希望对表进行收缩，使得浪费的空间不致太大。表收缩与表扩张是类似的:当表中的项数降的过低时，我们就要分配一个新的、更小的表，而后将旧表的各项复制到新表中。旧表所占用的存储空间则可被释放，归还到存储管理系统中去。在理想情况下，我们希望下面两个性质成立:
?动态表的装载因子具有一个常数下界，
?表操作的平摊代价具有一个常数上界。
另外，我们假设用基本插入和删除操作来测度代价。
关于表收缩和扩张的一个自然的策略是当向满表中插入一个数据项时将表的规模扩大一倍，而当从表中删除一项就导致表的状态小于半
133
满时，则将表缩小一半。这个策略保证了表的装载因子始终不会低于1/2，但不幸的是，这样又会导致各表操作具有较大的平摊代价。请考虑下面这种情况:我们对表T执行n次操作，此处n为2的整数幂。前n/2个操作是插入，由前面的分析可知其总代价为O(n)。在这一系列插入操作的结束处，num[T]=size[T]=n/2。后面的n/2个操作是下面这样一个序列:
I，D，D，I，I，D，D，I，I，...... 其中I表示插入，D表示删除。第一次插入导致表扩张至规模n。紧接的两次删除又将表的大小收缩至n/2;紧接的两次插入又导致表的另一次扩张，等等。每次扩张和收缩的代价为O(n)，共有O(n)扩张或收缩。
2这样，n 次操作的总代价为O(n)，而每一次操作的平摊代价为O(n)。
我们可以对这个策略加以改进，即允许装载因子低于1/2。具体来说，当向满的表中插入一项时，还是将表扩大一倍。但当删除一项而引起表不足1/4满时，我们就将表缩小为原来的一半。这样，表的装载因子的下界是常数1/4。这种做法的基本思想是使扩张以后表的装载因子为1/2。在发生一次收缩前要删除表中一半的项，因为只有当装载因子低于1/4时方会发生收缩。同理，在收缩之后，表的装载因子也是1/2。这样，在发生扩张前要通过扩张将表中项数增加一倍，因为只要当表的装载因子超过1时方能发生扩张。
我们略去了TABLE—DELETE的代码，因为它与TABLE—INSERT
134
的代码是类似的。为了方便分析，我们假定如果表中的项数降至0，就释放该表所占存储空间。亦即，如果num[T]=0，则size[T]=0。
现在我们用势能方法来分析由n个TABLE—INSERT和TABLE—DELETE操作构成的序列的代价。先定义一个势函数,，使得它在刚完成一次扩张或收缩时值为0，并随着装载因子增至1或降至1/4而变化。我们用,(T)=num[T]/size[T]来表示一个非空表T的装载因子。对一个空表，因为有num[T]=size[T]=0，且, (T)=1，故总有num[T]=,(T)，size[T]。无论该表是否为空，我们采用的势能函数为:
2,,numTsizeT[][]若,()/T,12, ,()T,,sizeTnumT[]/[]2,若()/T,12,,
请注意，空表的势为0，且势总是非负的。这样，以,表示的一列操作的总平摊代价即为其实际代价的一个上界。
在进行详细分析之前，我们先来看看势函数的某些性质。当装载因子为1/2时，势为0。当装载因子为1时，有num[T]=size[T]，这就意味着,(T)=num[T]。这样当因插入一项而引起一次扩张时，就可用势来支付其代价。当装载因子为1/4时，size[T]=4,num[T]。它意味着,(T)=num[T]。因而当删除某项引起一次收缩时就可用势来支付其代价。
为分析n个TABLE—INSERT和TABLE—DELETE的操作序列，
’我们用c来表示第i次操作的实际代价，c表示第i次操作的平摊代价，ii
num表示在第i次操作之后表中存储的项数，size表示第i次操作后表ii
135
的大小，,表示第i次操作后表的装载因子，,表示第i次操作后的势。ii开始时，num=0, size=0，,=1, ,=0。 00i0
我们从第i次操作是TABLE—INSERT开始分析。若,,1/2，则所i-1需要做的分析就与6.4.2中对表扩张的分析完全一样。无论表是否进行
’了扩张，该操作的平摊代价c至多是3。如果,<1/2，则表不会因该操ii-1作而扩张，因为仅当,=1时才发生扩张。如果还有,<1/2，则第i个操i-1i作的平摊代价为:
c’= c +,-,=1+(size/2-num)-( size/2-num) i iii-1iii-1i-1
=1+(size/2-num)-(size/2-(num-1))=0 iiii
如果,<1/2, 但,,1/2, 则 i-1i
c’= c +,-,=1+(2, num-size)- ( size/2-num) i iii-1iii-1i-1
=1+(2(num+1)- size)-(size/2-num) i-1i-1i-1i-1
=3,num-3/2 size+3 i-1i-1
=3, size-3/2 size+3 i-1i-1i-1
<3/2 size-3/2 size+3=3. i-1i-1
于是，一次TABLE—INSERT操作的平摊代价至多为3。
现在我们再来分析一下第i个操作是TABLE—DELETE的情形。这
时，num=num-1。 ii-1
如果,<1/2，我们就要考虑该操作是否会引起一次收缩。如果没有，i-1
则size=size，而该操作的平摊代价则为: ii-1
136
c’= c +,-,=1+(size/2 - num)- ( size/2-num) iiii-1iii-1i-1
=1+(size/2-num)-( size/2-(num+1)) iiii
=2
如果,<1/2且第i个操作触发一次收缩，则该操作的实际代价为i-1
c = num+1，因为我们删除了一项，移动了num项。这时，iiisize/2=size/4=num+1, 而且该操作的平摊代价为: ii-1i
c’= c +,-,=(num+1)+( size/2- num)- ( size/2- num) iiii-1iiii-1i-1
=(num+1)+((num+1)-num)-((2,num+2)-(num +1)) iiiii
=1
当第i次操作为TABLE—DELETE且,,1/2时，其平摊代价仍具i-1
有一个常数上限。有关这种情况的分析留作练习。
总之，因为每个操作的平摊代价都有一常数上界，所以作用于一动态表上的n个操作的实际时间为O(n)。
第七章 近似算法
?很多实际应用中问题都是NP-完全问题
?NP-完全问题的多项式算法是难以得到的
?求解NP-完全问题的两种方法:
?如果问题的输入很小，可以使用指数级算法圆满地解决该问题
137
?使用多项式算法求解问题的近似优化解
?近似算法:能够给出一个优化问题的近似优化解的算法 ?本章将介绍几个NP-完全问题的多项式时间算法
7.1 近似算法的性能分析
?本节讨论的问题是优化问题
?问题的每一个可能的解都具有一个正的代价 ?问题的优化解可能具有最大或最小代价——最大化或最小化问题 ?我们希望寻找问题的一个近似优化解
1. Ratio Bound
定义1(Ratio Bound) 设A是一个优化问题的近似算法，A具有ratio
*,,ccbound p(n)，如果, 其中n是输入大小，c是近似算法max,(),pn,,*cc,,
*所产生的解的代价，c是优化解的代价。
,,,,ccc, *若问题是最大化问题，则，,, cc,max，,,,,ccc,,
,,,ccc,,,*若问题是最小化问题，则cc,， max，,,,,,ccc,,
138
**由于c/c<1当且仅当c*/c>1, 近似算法的Ratio Bound不会小
,,,cc 于1，即 ,，,max,1,,,cc,,
*求解准确优化解的优化算法的Ratio Bound一定是1
*具有较大Ratio Bound的近似算法给出的近似解一定比优化解坏
的多 — Ratio Bound表示了近似算法的性能
2. 相对误差
cc,,定义2 对于任意输入, 近似算法的相对误差定义为, 其中cc,
*是近似算法所产生的解的代价，c是优化解的代价。
*相对误差总是非负的。
c,c,定义3 一个近似算法的相对误差界为如果。 ,(n),,(n)c,
结论1 ,(n),p(n),1。
,cc,,cc,c 证. 对于最小化问题,(n),===p(n),1 ,1c,c,c,
c,,1,cc,,p(n),1c,cc,p(n),1,(n), 对于最大化问题===. c,c,c,p(n)
c
139
*对于某些问题，和独立于输入n，我们用p和表示之 p(n),(n),
*对于另一些问题，很难找到具有固定ratio bound的多项式时间
算法，我们可以令ratio bound是输入大小n的函数
*某些NP-完全问题的近似算法满足:当运行时间增加时，ratio
bound和相对误差将减少
定义4 一个优化问题的近似模式是一个算法，是AI(，),AI(，),
,,0一个具有相对误差界的近似算法，其中I是问题实例，是任意一,
个固定的数。
定义5 近似模式AI(，),称为一个多项式时间近似模式，如果对于
I，AI(，),的运行时间是的多项式。 ,,,0
定义 6 一个近似模式称为完全多项式时间近似模式，如果它的运
1行时间是关于和输入实例大小n的多项式。 ,
21,,3 例1. 设模式s的运行时间是，则s是完全多项式时间近似n,,,,,
模式。
7.2 优化结点覆盖问题
140
1. 问题定义
输入:无向图G=(V，E)
'输出:，满足 VV,
'',,uvE, (1).，、或{u,v},V’ uV,vV,，，
' (2).是满足条件(1)的最小集合。 V
*理论上已经证明优化结点覆盖问题是NP-完全问题。
2. 近似算法
APPROX-Vertex-Cover (G)
1. C,,
'EEG,2. ,,
'3.while DO E,,
'uvE,,4. 任取 ，，
CCuv,:,5. ,,
6. E’?E’-{(u’,v’)|u’=u或v’=v}
7. Roturn C
141
3. 时间复杂性
T(G)=O(|E|).
4. 性能
定理1 Approx-Vertex-Cover 具有Ratio Bound 2
证: 令A=是算法第4步选中的边}。 (,)(,)uvuv,
E, 若(u,v),A，则所以与(u,v)邻接的边皆从中删除。
于是, A中无相邻接边.
于是，第五步的每次运行增加两个结点到C，,C,=2,A,
** 设C是优化解，C必须覆盖A。
* 由于A中无邻接边，C至少包含A中每条边的一个结点。
*** 于是，,A,,,C,，,C,=2|A|,2,C,，即|C|/|C|,2.
7.3 最小集合覆盖问题
1. 问题的定义
142
输入:有限集X，F是X的所有子集合集族，X= S:
S,F
输出:C,F，满足
, (1). X=S:
S,C
(2). C是满足条件(1)的最小集族，即|C|最小。
*最小集合覆盖问题是很多实际问题的抽象。
*最小集合覆盖问题是NP-完全问题。
2. Greedy近似算法
Greedy-Set-Cover(X,F)
1.U,X;
2.C,,;
3. While U,, Do /* U表示X中尚未被覆盖的元素的集合 */
4. select S,F 使得,S?U,最大;
/* Greedy选择——选择能够覆盖最多X元素的子集合S */
5. U,U-S
6. C,C?,S,; /* 构造X的覆盖 */
7. Return C.
143
3. 复杂性
?3-6的循环次数至多为min(,X,,,F,)
?,S?U,需要时间O(,X,)
?第4步需要时间O(,F,,X,)
?T(X,F)=O(,F,,X,,min(,x,,,F,))
4. 性能
d
1i令H(d)=。Greedy-Set-Cover具有Ratio Bound 定理1 ,i,1
H(max,,S,: S,F,)。
***证:设C是优化的集合覆盖, C的代价是,C,。令S是由i
Greedy-Set-Cover选中的第i个子集。设当把S加入C时, C的代价加i1。把选择S的代价均匀地分配到由S首次覆盖的所有结点。 ii
对于x,X，令c是分配到x的代价。若x被S首次覆盖,则 xi
1c=. xS,，，S,S.....,Si12i,1
显然，算法给出的解C的代价为,C,，,C,平均地分布到x的所有点.
*由于C也覆盖X，我们有
c,C,=,. c,,,xx*x,Xx,SS,C
144
*注意:上式的小于成立是因为C中各子集可能相交，在中，某c,,x*x,SS,C些c被加了多次，而在中每个c只加一次。 cxx,xx,X
c 如果,S,F，,H(,s,)成立，则 ,xxx,
*,C,,,,,C,,H(max,,S,: S,F,), H(S)c,,,x*S,C*x,SS,C
*即|C|/|C|,H(max,,S,: S,F,), 定理成立。
c 现在我们来证明:对于,S,F，,H(,S,)。 ,xxx,
对于,S,F和i=1,2,...,C,, 令u=,S-(S?S?...?S),是S、i12i1S、...、S被选中后，S中未被覆盖的点数。 2i
令u=,S,, k是满足下列条件的最小数:u=0, 即S中每个元素被S、k10
S、...、S中至少一个覆盖。 2k
显然，u,u, u-u是S中由S第一次覆盖的元素数。于是，i-1ii-1ii
被S第一次er的点数covi,,,,,k1。 c,(u,u),,,xii,1，，::S,S....SxSi,,1ii1,1,,,,,,,,,被S第一次Cover的点的分解的代价i
注意:,S-(S?S?...?S,,,S-(S?S?...?S,=u, 因为Greedi12i-112i-1i-1算法保证:S不能覆盖多于S覆盖的新结点数,否则S将在S之前被选中。 ii
k1c()uu,于是，,。 ,,i,1ixui,1xx,i,1
b11i对于任意整数a; 0
3. For i,1 To n Do
4. L,Merge-List(L,L+x); ii-1i-1i
5. 删除L中所有大于t的元素; i
6. Return L中最大元素. n
*Merge-List(L,L')合并L和L', 产生一个有序表.
*Merge-List(L,L')的时间复杂性为O(|L|+|L'|).
Exact-Subset-Sun(s,t)计算过程:
L=<0> 0
L=<0,X> /* 前一个元素所有子集的和 */ 11
147
L=<0,X,X,X+X> /* 前二个元素所有子集的和 */ 21212
L=<0,X,X,X+X,X,X+X,X+X,X+X+X> /* 前三个元素所有子集的和 */ 3121231323123
算法正确性:
令p={0}, p=,x , x=y,A,,x,x,...x,,,即p是,x,x,...x,的12ii12i0i,yA,
所有子集合的集合。p= p?(p+ p). 我们可以对i作数学归纳法，ii-1i-1i证明L是p中所有不大于t的元素的有序表。于是，算法是正确的。 ii
算法的复杂性:
i?,L,,2 i
12nn?T(S,t),1+2+2+...+2=O(2).
3. 完全多项式时间近似模式
?Trim算法
定义2(修剪表L) 设δ(0<δ<1)是修剪参数, L是一个表. 根据δ修
剪L是指:
(1). 从L中删除尽可能多的元素,
(2). 如果L'是L修剪后的结果, 则对于每个从L中删除的元素y, L'
148
中存在一个元素z,y, 使得(y-z)/y,δ或(1-δ)y,z,y.
*如果y被修剪掉，则存在一个代表y的z没有被修剪掉，而且z相
对于y的相对误差小于δ。
例. 如果δ=0.1, L=<10,11,12,15,20,21,22,23,24,29>, 则L修剪
为L'=<10,12,15,20,23,29>.
算法
输入:L=,y,y,...y,, y,y; 0<δ<1 12mii+1
, 输出:L: Trimed有序表
Trim(L,δ)
1. m,,x,
,2. L, 1
3. last,y 1
4. For i,2 To m Do
5. If last<(1-δ)y /* y<(1-δ)y, 即对于,y,L',不满足(1-δ)y,y */ i-1iii
,6. Then y加入到L末尾 /* L'中目前没有能够表示y的元素 */ ii
7. last, y i
,8. Return L
149
复杂性:T(L,δ)=0(,L,)=0(m)
?完全多项式近似模式
输入:S=,x,x,...x,, t,0, 0<,<1 12n
输出:近似解
Approx-Subset-Sum(S,t,,)
1. n,,S,
2. L,<0> 0
3. For i,1 To n Do
4. L,Merge-List(L,L+x) ii-1i-1i
5. L,Trim(L,,/n) /* 修剪参数δ=,/n */ ii
6. 从L中删除大于t的元素 i
7. 令z是L中最大值 n
8. Return z
定理1 Approx-Subset-Sum是子集求和问题的一个完全多项式时间
近似模式。
y证:如前所述，p= p?(p+ p)=,x , x=,A,,x,x,...x,,ii-1i-1i12i,yA,
150
是,x,x,...x,的所有子集合的和的集合, p={0}。L经第5步修剪以及12i0i第6步的大于t元素的删除，仍然有L,p。于是，第8步返回的z是SiI
的某个子集的和。
我们需证明
**** ?C(1-,),z,即(C-z)/C,,, C是优化解，z是Approx-Subset-Sum
**产生的近似解。注意，由于子集合求和问题是最大化问题，(C-z)/C是Approx-Subset-Sum的相对误差。
?算法是关于,S,和1/,的多项式时间算法。
*(1). 往证C(1-,),z
我们对i作归纳法证明:,y,p, y,t, 存在一个z',L使 ii
i(1-,/n)y,z',y.
当i=0时p={0},L={0},命题成立。 ii
设当i,k时命题成立。p= p?{p+x}。由归纳假设，,y,p?k+1kkk+1k+1
kk+1p,y,t,存在z',L,L使(1-,/n)y,z',y, 于是(1-,/n)y,z',y。而对kkk+1
于,y',p-p，y,=y+x,t,y,p,由归纳假设，存在z',L,L使 k+1kk+1kkk+1
k(1-,/n)y,z',y。
k于是，(1-,/n)y+x,z'+x,y+x。由于z',L，z'+x,L, 而且 k+1k+1k+1kk+1k+1
kk+1((1-,/n)y+x)-((1-,/n)(y+x)) k+1k+1
kk+1 =(1-,/n)(y-(1-,/n)y)+(x-(1-,/n)x)>0, k+1k+1
k+1k即(1-,/n)(y+x),(1-,/n)y+x,z'+x,y+x。 k+1k+1k+1k+1
151
*最后，如果C,p是子集合求和问题的优化解，则存在一个z',L， nn
n **使得(1-,/n)C,z',C。Approx-Subset-Sum返回最大的这样的z',即z。
,nd(1,)nn,0由于，(1-,/n)是关于n递增的函数。由于n>1, dn
n(1-,)<(1-,/n)。
*于是，(1-,)C,z，即Approx-Subset-Sum返回的z与优化解的相对误差不大于,。
(2) 往证Approx-Subset-Sum的时间复杂性是n与1/,的多项式。
我们推导,L,的上界。修剪以后，L中的相邻元素z和z'满足: ii
(z-z,)/z>,/n,
即，z/z,>1/(1-,/n)。如果L中具有k+2个元素，则必有:y=0, y=z, i010
2ky>z,1/(1-,/n), y>z,1/(1-,/n),…, y>z,1/(1-,/n), 而且2030k+10
kz,1/(1-,/n),t故L中元素至多为 0i
k+2=2+logt=2+(lnt/-ln(1-,/n)), 2+nlnt/,。 1/(1-/n),
算法的运行时间是,L,的多项式，即n和1/,的多项式。 i
7.5 Traveling-Salesman Problem (TSP)
7.5.1 问题定义
152
输入:完全无向图G=(V,E), 代价函数C:E?非负整数集合。
输出:具有最小代价的Hamilton环
* Hamilton环是一个包含V中每个结点一次的简单环。
*代价函数的扩展:设A,E，C(A)=。 C(u,v),(u,v),A
*三角不等式:C(u,w),C(u,v)+C(v,w).
*满足三角不等式的TSP问题是NP完全问题。
*不满足三角不等式的TSP问题更是NP完全问题。
*不满足三角不等式的TSP问题的近似算法没有常数Ratio bound，
除非NP=P。
7.5.2 满足三角不等式的TSP问题
1. 最小生成树算法
?问题定义
输入:无向连通图G=(V,E), 权函数W:E?非负整数集合。
输出:具有最小权的无环T,E。
153
*权函数的扩展:设T,E，W(T)=。 C(u,v),(u,v),T
?Prim算法
输入:无向连通图G，权函数W，生成树的根r
输出:最小生成树{(v, ,[v]) | v,V-{r}}
数据结构:Q:优先队列,在算法执行过程中始终存储G不在生成
树中的结点集合;
key[v]: 生成树中与v相邻接的所有边的最小权，如
果这样的边不存在，key[v]=,
,[v]:在生成树中v的父结点。
MST-Prim(G,w,r)
1 Q=V[G]; /* G的所有结点加入优先队列 */
2 FOR each u,Q DO
3 Key[u]=,;
4 key[r]=0; /* 令树根是目前具有最小key的结点 */
5 ,[r]=NIL; /* 树根无父结点 */
6 While Q,0 Do
7 u=EXTRACT-MIN(Q);
/* 从Q中取出具有最小key的结点u，u连接(V-Q,Q) */
8 For each v,Adj[u] Do /* 考察每个与u邻接的结点
154
*/
9 If v,Q and W(u,v)1, 则没有Ratio Bound为p的求解一般TSP
157
问题的近似算法。
证:
我们使用反证法。设P,NP，而且对于某个p>1，存在一个Ratio Bound为p的求解一般TSP问题的近似算法A。不失一般性，我们假定p是一个整数。
往证我们可以使用A在多项式时间内解决哈密顿环问题。哈密顿环问题是NP完全问题。如果A能够在多项式时间内解决哈密顿环问题，则P=NP，与P,NP矛盾。
令G=(V,E)是哈密顿回路问题的任意一个实例。
我们首先把G=(V,E)转换为TSP问题的一个实例(G’,C)。构造完全图G’=(V,E’)和权函数C如下:
E’={(u,v)|u,v,V, u,v}.
,1 if (u,v),E,C(u,v)=. ,p|V|，1 otherwise,,
显然，我们可以在|V|和|E|的多项式时间内由G建立出G’和C。
一方面，如果G中具有一个哈密顿环H，则C分配给H的每条边的代价为1，因此(G’,C)包含一个代价为|V|的哈密顿环。
另一方面，如果G中不具有一个哈密顿环，则G’中的哈密顿环必须
158
必包含不在E中的边。这样的环的代价至少为
(p|V|+1)+(|V|-1)>p|V|.
用算法A去解哈密顿环问题:如果G包含一个哈密顿环，A一定返回它(因为它的代价最小);如果G中不包含哈密顿环，则A返回一个G’的哈密顿环H，H的代价大于p|V|.
求解哈密顿环问题的多项式算法为:
G=(V,E)
变换算法
(G'=(V,E'),C)
算法A
H
C(H)>p|V|
ny
G中无 G中由
哈密顿环哈密顿环
由于变换算法和A都是多项式时间算法，上述算法是多项式算法。于是，P=NP。
第八章 随机算法的设计与分析
159
8.1 基本概念
?随机算法
随机算法是一种使用概率和统计方法在其执行过程中, 作出随机
选择的算法。
*随机算法既使对于一个固定的输入，其行为也是随机的。
?随机算法的设计
在算法的选择决策点，使用概率与统计方法作出随机选择。主要
方法包括:
?随机抽样
?随机生成，如随机数
?随机算法的分析
证明随机算法在每个输入上都以很高的概率有效地工作。
*随机算法的分析与非随机算法的平均复杂性分析不同。平均
复杂性分析是根据不同输入的概率计算复杂性均值。而随机
算法的分析对于每个输入都要考虑算法的概率统计性能。
?本章内容
通过以下随机算法实例介绍随机算法的设计与分析方法:
?随机化选择算法
?随机化QUICKSORT算法
8.2 随机化选择算法
8.2.1 问题定义
输入:S={x, x, …, x}，整数k，1,k,n。 12n
输出:S中第k个最大元素。
160
8.2.2 随机算法
1. 记号
t,Q=集合Q中的元素t的rank (第k个最大元素的rank是k)。
i,Q=集合Q中第i个最大元素。
2. 算法
输入:S={x, x, …, x}，整数k，1,k,n。 12n
输出:S中第k个最大元素，k,S.
LAZYSELECT(S, k)
3/41. 独立、均匀、可放回地从S中随机选择n元素，并存入R;
2. 在O(nlgn)时间内排序R;
3/43/4-1/4 3. x=(k/n) n; /* (k/n) n=kn*/ 3/4x,nx，n4. l=max{, 0}; h= min{, n}; ，，，，
5. L=l,R; H=h,R;
6. 确定L,S和H,S;/* 把L和H与S的每个元素比较 */
7. P={y,S | L,y,H};
3/48. If k,S,P and |P|,4n+1 /* k,S,P可由L,S,k,H,S确定 */
9. Then 排序P，确定(k-L,S),P=k,S, 算法结束;
10. ELSE goto 1.
3. 算法分析
?数学基础
(1) 数学期望:
?离散随机变量X的数学期望E[X]=i，p(X,i)。 ,
i
?如果f(x)是定义在整数集合上的实数值函数，则
E[f(X)]=f(i)，P(X,i). ,
i
(2) Markov不等式:
?P(Y,t),E[Y]/t, 其中Y为非负随机变量，t>0.
(3) 方差与Chebyshev不等式
22σ?方差 =E[(X-,)]，其中,为随机变量X的数学期望 xxx
161
2?标准差 σ,E[(X,μ)]xx2?Chebyshev不等式:P(|X-,|>t,),1/t xx
2σ ?如果随机变量X满足P(X=1)=p，P(X=0)=1-p，则=p(1-p). x
mm22Xσσ ?如果X=, 则=，其中X是独立随机变量。 i,,xixii,1i,1
2σ ?如果随机变量X满足P(X =1)=p，P(X =0)=1-p，则=mp(1-p). iiix
?算法分析
定理1. LASYSELECT算法执行1-9一遍就可以求出k,S的概率是
-1/41-O(n)，即LASYSELECT算法需要2n+O(nlgn)次比较就可以求出k,S
-1/4的概率是1-O(n)。
证:
如果LASYSELECT算法执行1-9一遍就可以求出k,S, 则第6步需要2n次比较, 其他步骤需要O(nlgn)次比较。于是总的需要2n+O(nlgn)次比较。
我们需要证明的是:LASYSELECT算法执行1-9一遍就可以求出
-1/4k,S的概率是1-O(n)。
LASYSELECT算法执行1-9一遍就可以求出k,S的条件是:
(1). k,S在L和H之间，
3/4(2). |P|,4n+1且P包含k,S。
我们首先来计算上述两个条件失败的概率。
A. 计算条件(1)不成立
条件(1)不成立当且仅当L>k,S或H< k,S。
令X=1如果第i个随机样本,k,S，否则X=0。于是P(X=1)=k/n, iii3/4n
P(X=1)=1-k/n。令X=是R中小于等于k,S的样本数。我们有 Xi,ii,13/4-1/4?X的数学期望,=kn/n=kn, x
3/423/4σ?X的方差=n(k/n)(1-k/n),n/4, x3/8σ?X的标准差,n/2。 x
nn
L , H x
162
如果L>k,S, XH>,. 于是 xx
P(L>k,S)=P(,,X+n)= P(,-X,n)= P(|X-,|,n), xxx
P(Hk,S)= P(Hk,S。类似与上面A中lh的分析，
-1/4P(L< k,S)= P(H>k,S)= O(n)。 lh
显然，“LASYSELECT算法执行1-9一遍就可以求出k,S”不成立
-1/4的概率是O(n)。于是，“LASYSELECT算法执行1-9一遍就可以求出
-1/4k,S”的概率是1-O(n)。
8.3 随机化QUICKSORT算法
8.2.1 问题定义
输入:S={x, x, …, x}。 12n
输出:排序的S。
8.2.2 随机算法
1. 算法
输入:S={x, x, …, x} 12n
输出:数组A:包含排序的S
random_quicksort(S)
1. IF |S|,24, 使用通常的方法排序S;
2. 随机地选择S的一个元素M(S);
3. M(S)与S的每个元素比较，把S划分为两个集合
163
S={ s | s,S-{M(S)}, s,M(S)} 1
S=S-{M(S)}-S; 21
4. A= random_quicksort(S); 11
5. A= random_quicksort(S); 22
6. A=A联接M(S)联接A。 12
2. 算法分析
?数学基础
引理1 设我们投掷一枚硬币，投掷一次出现正面的概率为p。如
果连续投掷，直至第一次出现正面所需要投掷的次数的数
学期望为1/p.
引理2 P(),. P(A)A,:iiii
?算法分析
定理1 对于每个输入，算法random-quicksort的运行时间的数学期望不大于(4/3)nlogn+O(n)。
证:
设随机变量X是random-quicksort运行期间划分点与S的元素比较的次数(包括递归调用中需要的比较次数)。我们来计算E[X]。
?确定X的取值范围
最好情况: 每个划分点都是集合的中值，递归层次为logn, X为 2
,(nlogn). 22 最坏情况:每个划分点都是集合的最小值，X为, (n).
?往证E[X]取值O(nlogn)
nn令n是e,S与划分点比较的次数，则X=。E[X]=。nE[n],,iiiii,1i,1我们只需要证明E[n]=O(log n), 则E[X]=O(nlogn)。令 i
S(i)=S, 0
S(i)=第一次划分后S的包含e的子集合， 1i
……，一般地
164
S(i)=S(i)的包含e的子集合，如果M(S(i))=e, 则S(i)无定义。 j+1jijij+1
我们说第j步划分对e是成功的，如果: i
|S(i)|,(7/8)| S(i)|或M(S(i))=e. j+1jji
第j步划分不成功如果:
(1) S(i)中| S(i)|/8个最小(或最大)元素之一被选中为划分点 jj
(2) e不是M(S(i)) ij
第j划分步不成功的概率是 ((1/8)+(1/8))p<1/4, 其中p是“e不是iii
M(S(i))”的概率。于是，第j划分步成功的概率是3/4。 j
以下所有的对数都是以8/7为底的对数。
k设涉及e的成功的划分步数为k，则(7/8)n,24。从而，k,log(n/24)。 i
令随机变量Y是从第k-1对e成功步到第k对e成功步所需要的kii
log(n/24)log(/24)nYE[Y]成功步数。显然，n=，E[n]=。由于每一划分步成功,,iikk1k,1k,
的概率是3/4以及引理1，从第k-1成功步到第k成功步所需要的划分
步数的数学期望最多是1/(3/4)=4/3。于是，E[Y],4/3。E[n]=(4/3)log(n/24) ki
, (4/3)logn. 于是，E[X]=O(nlogn)。
算法第1步需要执行n/24次，每次需要276个比较(24个元素的
(n/24)=O(n). 所有对之间比较次数为276)，总的比较次数是276
综上所述，对于每个输入，算法random-quicksort的运行时间的数
学期望不大于(4/3)nlogn+O(n)。
-6定理2. With probability 1-O(n), the random-quicksort algorithm
terminates in fewer than 21nlogn steps.
-7Proof. We will show that P(n>20logn),n. Letting the ith bad event A ii
be ―n > 20 logn‖, we have i-7-6P() , P(A),n×n=n. A,:iiii-6Thus, it would follow that with probability 1-O(n), n,20logn for all i, so i
nthat the total work is O(nlogn) with probability very close to 1 as n ,ii
becomes large.
The crucial observation is that since the choices of the splitters at
various levels of recursion are independent, the events that various
partitioning steps are successful are independent. What is the probability
that e goes through as many as 20logn-log(n/24) unsuccessful partitioning i
steps in 20logn attempts, each having a probability less than 1/4 of failure?
165
Such trials are like the tosses of a coin, and are called Bernoulli trials. Let Y
denote the number of unsuccessful partitioning steps in 20logn Bernoulli
trials, each of probability , 1/4. Now,
P(Y>20logn-log(n/24)),P(Y>19logn).
We bound the latter from above
,,,,nn20log20log20logn,j131jj,,,,()()(). ,,,,,,,444j,19lognj,19lognjj,,,,
Each term of the first summation considers all the possible ways of having j
unsuccessful steps, multiplied by the probability of j failures and 20logn-j successes. The independence of the various steps allows us to write this j20logn-jprobability as (1/4)(3/4).
n,,k,,Using the identity , we bound the above by ,(ne/k),,k,,
j20elogn5elognjj(),(),(5e/19). ,,,4j19logn)j,19lognjn,,19loglognj19
-7.5The latter is a geometric series and sums to O(n), which is better than -6what we wanted. Thus we have: ―With probability 1-O(n), the random-quicksort algorithm terminates in fewer than 21nlogn steps.‖
第九章 并行算法的设计与分析
9.1 并行计算机系统的发展
自从四十年代第一台电子计算机问世以来，计算技术的发展异常迅速，对人类活动的各个方面都产生了深刻的影响。伴随着计算机的迅猛发展，计算机应用日新月异，从科学计算到人类智能的模拟，对计算机的处理能力提出了越来越高的要求。提高计算机的处理能力一直是计算机发展的源动力。计算机科学家一直在追求三,(Trillion，万亿)目标，即:每秒一万亿次的运算速度，一万亿字节的存储容量，每秒一万亿字节的数据通信能力。这三个目标的每一个都是现有超级计算机性能的一千倍。
在计算机问世后的数十年间，计算机始终沿袭着Von Neumann计算机结构的顺序操作方式。提高计算机的速度一直被认为是加快时钟频率。到70年代初，顺序运行速度的提高显著地减慢了，其主要原因是元器件的速度已接近物理极限。人们开始了新的探索。以Cray为代表的计算机科学家企图在这个瓶颈周围探索一条迂回道路。他们把器件更紧密地组合在一起以便最大限
166
度地减少电讯号的传递距离，并采用了新的电路散热技术。同时，他们也采用了并行化技术。 他们把CPU分成若干相互协作的子单元，并把这些子单元装配成一条计算流水线。这种方法导致了并行向量处理计算机系统的出现。 CRAY RESEARCH公司的CRAY1和CRAY2计算机系统、日本NEC公司的SX-3计算机、日本富士通公司的VP-2600等都是并行向量处理系统的典型实例。这些机器的运算速度最多只达到5.5Gflops，距离每秒一万亿次还相距甚远。 日本的计算机制造
CRAY寄希望于延用老的设计，使用砷化镓芯片取代硅芯片，以取得更高的速度。砷化镓者和
芯片是以故障率高而昭著于世的。这种选择是一场代价昂贵的赌博。即使这种砷化镓计算机能够成功，也只能达到20Gflops的速度，距离一万亿次计算速度还相差50倍。
追求三,目标的另一种探索是增加计算机系统中处理器的数量。这种探索导致了大规模并行计算机(MPP)的出现。MPP计算机把大量的处理器集中在一起，以获得高速度。它把逻辑部件、存储器和通信网集成一体。通常，MPP计算机中的单个处理器的速度要比CRAY1的处理器慢，但是当我们把一个问题分解成许多子问题时，这个处理器集群就能以极高的速度来解决这个问题。第一台多处理器并行计算机Illiac是在1975年投入运行的。Illiac?是一台由64个处理器组成的阵列式并行计算机。1982年，CRAY X-MP诞生。它把两台CRAY1处理器组合在一起。两个处理器共享一个公共存储器。两个处理器可以执行不同的指令流。CRAY X-MP是第一台超过CRAY1计算机的计算速度的超级计算机。1987年，Daniel Hillis的Connection Machine(CM)问世。CM计算机是一台彻底摆脱了Von Neumann结构的MPP计算机。 CM计算机问世后不仅站住了脚，而且取得了举世瞩目的迅猛发展，CM1、CM2和CM5先后投入市场。 CM计算机的出现使人们相信， 具有数万、数十万个处理器的MPP计算机有可能达到三,目标。1990年以来，越来越多的多处理器并行计算机系统开始投入市场，如nCUBE、IPSC/2、Wavetracer、Multimax、Symmetry、FX/8、CRAY YMP、CM2、CM5等。目前多处理器并行计算机已经成为计算机领域的一场革命，推动了计算技术发展。
9.2 并行计算机系统的分类模型
并行计算机系统的分类方法很多。我们使用二维分类方法对并行计算机系统进行分类。所有并行计算机系统可以视为图9.2.1所示的二维空间的子集合。图9.2.1所示的并行计算机系统空间的第一维，即“存储器”维，把并行计算机系统分为两类。第一类是具有共享存储器的并行计算机。第二类是具有分布式存储器的并行计算机。“指令流,数据流”维把并行计算机系统分类为SISD、SIMD、MISD和MIMD四种并行计算机系统。下边我们以“指令流,数据流”为主，讨论各类并行计算机系统模型。
167
存储器
分布式存储器
共享存储器
指令流/数据流SISDSIMDMISDMIMD
图9.2.1.并行计算系统空间。
9.2.1 SISD计算机系统
SISD表示“单指令流单数据流”。SISD计算机系统由一个处理器、一个控制器和一个存储
器系统组成。存储器系统由多个存储模块组成。这类计算机系统包括了所有单处理器计算机系统。具有流水线并行性的向量计算机也包括在这一类计算机中。图9.2.2描述了SISD计算机系统的结构。
SISD计算机系统的处理器仅接收和处理单个指令流，而且这个指令流仅在一个数据流上执行。在SISD计算机的每步计算中，控制器向处理器发出一条指令，处理器在一个来自存储器的数据上执行这条指令。SISD计算机只有共享存储器一种类型。处理器对多个存储部件的存取由连接网络实现。
实际上，SISD计算机是传统的Von Neumann计算机。
单处理存储数令部件器据指据流(数单(连接网络令(指指令数流流存储令据控制部件指器
图9.2.2.SISD计算系统结构。
9.2.2. MISD计算机系统
MISD表示“多指令流单数据流”。MISD计算机系统的结构如图9.2.3所示。
168
...控制器控制器控制器
指指指令令令流流流
...处理器处理器处理器
数据流
连 接 网 络
存储存储存储...部件部件部件
图9.2.3.MISD计算机系统结构。
MISD计算机系统由多个处理器组成。每个处理器都有自己的控制器。所有处理器共享由多个存储部件组成的存储器。连接网络实现多个处理器对多个存储部件的存取。系统中每个处理器执行一个独立的指令流。多个处理器同时在一个数据流上工作。在MISD计算机系统的计算过程中，每个处理器都在同一个来自存储部件的数据流上执行自己的指令流。MISD计算机系统是并行计算机系统。它的并行性体现在多个处理器并行地完成不同的任务。我们来看一个MISD计算机系统的应用实例。
给定一个n维组数Z。我们要判别Z中的n个数是否素数。为了完成这个任务，我们需判别Z中每个数Z[i]是否仅能被,和Z[i]本身整除。为了容易说明，我们假设每个Z[i]有P个可能因子，记作f、f、...、f。下边是用一个具有P个处理器的MISD计算机系统判别Z中的n个数是否素i1i2iP
数的并行算法:
FOR i=1 TO n DO
从存储器读Z[i]，送到所有P个处理器;
FOR j=1 TO P DO (并行地)
从存储器读f, 送处理器j; ij
ENDFOR;
FOR j=1 TO P DO (并行地)
处理器j判别f是否可整除Z[i]; ij
ENDFOR;
IF P个处理器都回答“不能整除” THEN Z[i]是素数;ELSE Z[i]是合数;ENDIF;
ENDFOR。
从上述算法可以看到, 使用MISD计算机系统，P个处理机一次并行判别就可知Z中的一个数是否素数。如果使用单处理器计算机，P次判别才能给出回答。如果Z[i]的可能因子多于P个，读者可以自行修改上述算法，完成Z[1]、Z[2]、...、Z[n]是否素数的判别。
显然，MISD计算机系统只有共享存储器一种类型。
169
9.2.3 SIMD计算机系统
SIMD计算机系统是一类非常重要的并行计算机系统。SIMD表示“单指令流多数据流”。SIMD计算机系统分为两种。一种是共享存储器的SIMD计算机系统。另一种是具有多布式存储器的SIMD计算机系统。前一种又称为紧耦合SIMD计算机系统。后一种也称为松散耦合SIMD计算机系统。
控制器
PEPEPE
处理器处理器处理器
...
存储器存储器存储器
连 接 网 络
松散耦合SIMD计算系统结构。图9.2.4.
图9.2.4描述了松散耦合SIMD计算机系统的结构。松散耦合SIMD计算机系统包括一个控制器和多个处理单元(简称PE)，每个PE具有自己的存储器。多个PE由一个连接网络连接在一起。控制部件向多个PE广播指令。所有处于活动状态的PE同时执行由控制器广播的相同指令。于是，系统中只有一个指令流。每个PE在各自存储器的数据上执行控制器广播的指令。于是，系统具有多个数据流。连接网络用来实现PE间的通信。连接网络把每个PE连接到所有或部分其它处理器。一个数据传送指令可以使每个处于活动状态的PE向所有与它相连接的PE发送一个数据。在不直接连接的两个PE之间传送数据需通过中间PE间接进行。例如，假设PE仅连接到PE，PE011仅连接到PE。要从PE传递数据D到PE，D必须先传递到PE，然后再由PE传递到PE。 202112
图9.2.5给出了紧耦合SIMD计算机系统的结构。紧耦合SIMD计算机系统的多个处理器共享一个全局存储器。全局存储器由多个存储器模块组成。控制器仍然负责向多个处理器广播指令。所有处于活动状态的处理器在来自存储器的不同数据上同时执行由控制器广播的相同条指令。紧耦合SIMD计算机系统的连接网络把每个处理器连接到所有或部分存储器模块。它也把每个存储模块连接到所有或部分处理器。一个数据传送指令可以使每个处理器把数据传送到它所连接的一个或多个存储块，也可以把每个存储模块中的数据传送到它所连接的一个或多个处理器。处理器之间的数据通信可以通过共享存储器实现。如果两个处理P和P都与存储器模块M连接，12
170
P和P之间的数据通信可以通过M实现。如果P和P之间无直接相连的共享存储器，但P和P121213直接与存储器模块M相连接，P和P直接与存储器模块M相连。如果P要把数据,传送到1332321P，P需先把,传送到M，然后P把M中的,传送到M。P可以从M中得到P送来的2113313322321
D。 数据
控制器
...
处理器处理器处理器
连 接 网 络
...存储器存储器存储器
模块模块模块
紧耦合SIMD计算系统结构。图9.2.5.
第一个SIMD计算机系统是Illiac ?计算机。目前最大的SIMD计算机系统是CM2计算机。它包括65536个处理器。CM5计算机也具有SIMD的特点。下边我们来看一个SIMD计算机系统应用的例子。设X、Y和Z是三个向量。试求向量X与Y的和，并将结果存入Z。完成这个任务的单处理器计算机程序可以写为:
FOR i=0 TO N-1 DO Z(i):=X(i)+Y(i); ENDFOR. 然，这个程序在单处理器计算机上需要执行N步。 设X、Y和Z存储在具有N个处理单元的SIMD计算机中，如图9.2.6所示。要完成上述任务，SIMD计算机系统只需执行一条指令:Z:=X+Y。
171
控制器
PEPEPE
处理器处理器处理器
...X(1)X(0)X(N-1)Y(1)Y(0)Y(N-1)Z(1)z(0)Z(N-1)
连 接 网 络
向量X、Y、Z在SIMD计算机系统中的存储。图9.2.6.
我们把上述例子略作修改，可得如下程序:
FOR i=1 TO N-1 DO
Z(i) := X(i)+Y(i-1);
ENDFOR;
Z(0) := X(0).
设X、Y、Z仍然如图2.2.6所示的那样存储在SIMD计算机系统中。SIMD计算机系统可以按如下步骤完成这个计算:
1. FOR i=1 TO N-1 DO (并行地)
通过连接网络把Y(i-1)从PE移到PE; i-1i
2. ENDFOR;
3. 使PE处于不活动状态; 0
4. FOR i=1 TO N-1 DO (并行地)
PE完成 Z(i) := X(i) + Y(i-1); i
5. ENDFOR;
6. 使除PE以外的其它PE处于不活动状态; 0
7. PE完成 Z(0):=X(0). 0
这个例子说明了处理单元间连接网络的必要性，也说明了SIMD计算机系统应能使某些处理单元处于活动状态或不活动状态。
172
2.2.4 MIMD计算机系统
MIMD表示“多指令流多数据流”。MIMD计算机系统由多个处理器、多个控制器、多个存储模块和连接网络组成。每个处理器执行自己的程序。于是，MIMD计算机系统具有多个指令流。每个处理器在它自己的数据流上执行自己的指令流。所以，MIMD计算机系统具有多个数据流。连接网络用来实现处理器之间或处理器与存储模块之间的数据通信。在SIMD计算机系统中，处理器同步地使用连接网络。而在MIMD计算机系统中，各处理器独立异步地使用连接网络。MIMD计算机系统分为紧耦合和松散耦合两类。图9.2.7给出了紧耦合MIMD计算机系统的
MIMD计算机系统中，所有处理器共享多个存储模块。连接网络实现处理器与结构。在紧耦合
存储模块之间以及处理器与处理器之间的通信。
...控制器控制器控制器
处理器处理器...处理器
连 接 网 络
存储器存储器存储器...模块模块模块
紧耦合MIMD计算系统结构。图9.2.7.
图9.2.8给出了松散耦合MIMD计算机系统的结构。这类计算机系统由多个处理单元和一个连接网络构成。每个处理单元PE由控制器、处理器和自己的存储器组成。连接网络实现处理单元之间的通信。
PEPEPE
控制器控制器控制器
处理器处理器处理器...
存储器存储器存储器
连 接 网 络
图9.2.8.松散耦合MIMD计算系统结构。
MIMD计算机系统与SIMD计算机系统的主要区别在于前者的处理器异步独立运行，后者的处理器同步运行。MIMD计算机系统具有很大的灵活性，程序设计比较困难，要求比较复杂的
173
同步机制。很多应用都要求使用MIMD计算机系统。目前已经出现了很多MIMD计算机，如nCUBE、IPSC/2、Wavetracer、CM5等。由高速通信网连接的多计算机系统也可以视为一台MIMD计算机。我们在讨论支持并行数据库的并行计算结构时提到的SM并行计算结构是紧耦合MIMD计算机系统特例，SD和SN并行计算机结构是松散耦合MIMD计算机系统的特例。
9.3 连接网络
在9.2节我们已经看到，连接网络是并行计算机系统的关键组成部分，关系到多处理器(或多计算机)的通信方式和多存储模块的存取模式，对并行算法和并行程序设计具有十分重要的影响。连接网络的目标是以最小的造价提供快速灵活的通信方式。为了达到这个目标人们提出了大量的连接网络。每种连接网络都有其优点和缺点，但是没有一种连接网络在任何情况下都是最优的。连接网络分为动态连接网络和静态连接网络两类。
9.3.1 动态连接网络
动态连接网络主要用于共享存储器并行计算机系统结构，实现多处理器对多存储器模块的共享存取。本小节介绍几种比较重要的动态连接网络。
1. 共享总线连接网络
共享总线连接网络是最简单的动态连接网络。共享总线网络既可以用来实现多处理器对共享存储器的存取，也可以实现多处理器之间的通信。图9.3.1的(a)图给出了共享总线连接网络的实例。共享总线连接网络具有最简单的结构，也具有最严重的资源竞争，通信效率很低。
处理器处理器处理器处理器...处理器处理器...
...cachecachecache
共 享 总 线 连 接 网 络
共 享 总 线 连 接 网 络
存储器存储器存储器存储器存储器存储器...... 模块 模块 模块 模块 模块 模块
(b)(a)
图9.3.1.共享总线连接网络。
为了减轻共享总线的瓶颈问题，很多基于共享总线连接网络的并行计算机系统都使用了高速缓冲器技术。每个处理器设置一个局部高速缓冲器(Cache)。每个处理器可以预先把其即将使用的数据预先从共享存储器中读入局部高速缓冲器。这样，局部高速缓冲器就减少了处理器对共享存储器的存取次数，从而减轻了共享总线的瓶颈问题。图9.3.1的(b)图给出了具有局部高速缓冲器的共享总线连接网络结构。
174
2. 交叉开关网络
交叉开关网络主要用于实现多处理器对多个存储模块的共享，使所有处理器能够并行地存取所有存储模块。与共享总线相反，交叉开关网络具有最少的资源竞争，但具有最高的硬件复
.3.2给出了交叉开关网络的例子。图中的每个小圆圈表示一个开关。 杂性。图9
...存储模块存储模块存储模块
处理器
...
处理器
...
...
...
处理器
图9.3.2.交叉开关连接网络。
3. 蝶形连接网络
蝶形连接网络是与快速傅立叶变换(FFT)密切相关的连接网络。一个K-维蝶形连接网络具有
KK+1(K+1)2个开关结点和K2条边。一般地说，每个开关具有n个输入端和n个输出端。每个输入端可以与任何一个输出端连通。在任意时刻，一个输入端能而且只能与一个输出端连通，反之亦然。我们称这样的交叉开关为n×n开关。下边是一个2×2开关的两种连通状态:
直接连通交叉连通
K 蝶形连接网络的开关结点分为2行(或维)和K+1级。每个开关结点对应一个序对(w,i)，其中i是这个结点的级或维，w是这个结点所在行号的二进制表示。设i
协议
离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载
，也支持CMU自行设计的RMP(Reliable Message Protocal)等协议。
为了解决通信瓶颈问题，Nectar系统采用了高速光纤网，数据传输率可以从每秒100兆位到
每秒800兆位。此外，Nectar系统还采用了两种方法来降低通信延迟。一是减少数据发送与接收时数据复制的次数。由于结点机主存带宽的限制，频繁的数据复制将引起很大的通信延迟。二是与通信有关的中断处理均由通信加速器完成，减少结点机中断次数。为了进一步减少通信延迟，Nectar系统采用了图9.4.2所示的方法设计节点机与网络的接口。这种设计把用户数据缓冲区移到通信加速器中。因此，发送或接收数据时不需要由结点机来控制数据的复制操作。数据的打包和拆卸等工作在通信加速器上由用户进程Server完成。这样，由主存带宽限制所引起的通信延迟被降到最低。如果采用通常的方法，计算机向网络传送数据时，其接口过程如图9.4.3所示。用户命令被解释为某种系统调用，由该系统调用控制向网上发送数据。在执行系统调用时，首先由结点机操作系统从用户空间复印数据到系统缓冲区，经过数据打包后传送给网络控制器，然后从网络控制器转发到网上。使用这种方法，每发送或接收数据时，至少需要占用三次总线，引起很大的通信延迟。
节点机节点机节点机
通讯加速器通讯加速器通讯加速器
......
光纤端口光纤端口光纤端口
交换器交换器交换器
光纤端口光纤端口光纤端口
Nectar网
......
通讯加速器通讯加速器通讯加速器
节点机节点机节点机
图9.4.1.Nectar系统结构示意图。
191
在Nectar网中，每台结点机通过交换器实现与其它结点机的直接点对点通信，数据传输率不随计算机结点的增加而下降。Nectar的围绕一组核心为1616交叉开关的交换器而设计。交换，
器能够使结点机的通信加速器“打开”或“关闭”。通信加速器可以实现数据包和非数据包方式的信息传输。按数据包方式传输信息时，数据以包的形式传送，数据包的最大长度受到交换器
FIFO缓冲区的长度限制。 按非数据包方式传输信息时，传送数据的长度不受限制。根据端口
测定，Nectar网络进行数据传送时，数据包第一个字节的传送延迟(包括建立链路和完成传送两部分)约为0.7毫秒，其余字节传送时的延迟时间为0.35毫秒。Nectar的交换器能够在每0.7毫秒的周期内建立一个新的链路。
由于单个交换器的传送和开关延迟较低，多个交换器组成的网络结构附加的延迟也较少。CMU的实验表明，通过增加交换器的个数，Nectar网可以支持近100台工作站构成的机群并行计算系统。
CPU
用户数据主存储器 缓冲器
通讯加速器
网络
节点机与网络的接口过程。图9.4.2.
CPU
用户系 统存储器空间缓冲区
主存储器网络控制器
网络
图9.4.3.一般的数据传递接口过程。
192
2. Hcluster系统
Hcluster是黑龙江大学信息技术研究所研制的微型计算机机群并行计算系统。 Hcluster并行计算系统目前由16台586高档微型计算机组成。16台计算机由我们自行研制的16台通信处理器和互连网络连接成4维Hypercube并行计算结构。Hcluster的系统结构如图9.4.4所示。
处理处理处理处理结点结点结点结点
处理处理处理处理结点结点结点结点处理处理处理处理结点结点结点结点
处理处理处理处理结点结点结点结点
图9.4.4. Hcluster的系统结构。
图9.4.4中的每个处理结点由一台586微型计算机和一台通信处理器构成，其结构如下:
586微型计算机
通信处理器
每个通信处理器由一台微处理器、通讯接口和高速缓冲器组成。
为了解决网络瓶颈问题，Hcluster摆脱了局域网络的束缚， 使用了一个具有Hypercube拓扑结构的通信网络。这个网络具有如下的特点:
1. 具有通信性能很高的Hypercube
2. 突破了总线式通信网络的局限性，实现了网上多计算机并行通信, 即多计算机可同时在
3. 实现了网络物理链路的多位并行信息传输,
4. 实现了计算与通信过程的重叠，提高了系统的并行性。
5.
目前，Hcluster的信息传输率峰值可达每秒300兆位。 如果使用高速元器件，信息传输率可达每秒千兆位。Hcluster已经用于实现并行数据库管理系统。实验表明，Hcluster具有很高的效率和性能。
193
9.4.4 机群并行计算系统的软件环境
我们在9.4.3节介绍了机群并行计算机系统的硬件环境。显然，仅有硬件环境，机群并行计算系统还不能有效地支持并行程序的开发和运行。软件开发环境是机群并行计算机系统必不可少的重要组成部分。最近几年，出现了一些基于机群并行计算机系统的软件开发环境，其中影
Express系统。本节简单介绍一下这两个系统。 响较大的是PVM和
1. PVM并行软件环境
PVM(Parallel Virtual Machine)是一个以UNIX基础，以TCP/IP为通信协议的并行计算机机群软件环境。PVM把多个异构计算机通过网络互连在一起，构成并行虚拟计算机系统。PVM是由美国OAK RIDGE国家实验室于1989年开始研制的系统。田纳西大学、EMORY大学和卡内基—梅隆大学也参加了PVM的研制工作，并得到了美国能源部、国家自然科学基金、CONVEX公司
年初推出了3.3.7版。1995年9月推出了3.3.9版。与PVM配套的异构计和田纳西州的资助。1995
算机网络环境HeNCE和可视化工具XPVM已经被推广使用。很多标准软件系统正在移植到PVM平台。
PVM支持的结点机可以是并行机、向量机、工作站等，网络可以是ETHERNET、FDDI等。在这个机群并行计算软件环境中，用户可以指定其中的任意一台结点机为主机。PVM中并行执行的基本单位是任务。任务与UNIX的进程类似，通常就是一个UNIX进程。PVM的基本功能就是支持多任务在多个结点机上并行执行。PVM提供了控制多任务并行执行和实现多任务间通信同步的软件工具。PVM支持FORTRAN和C语言。
PVM软件环境由两部分组成。第一部分是PVMD。PVMD运行在所有结点机上。用户使用PVM时，首先需要在一个网络结点机上执行PVMD。这个结点机上的PVMD将启动其它节点机上的PVMD，共同组成一个由用户定义的虚拟并行计算机。应用程序可以在任一结点上执行。多个用户可以配置多个相互重叠的虚拟机。每个用户可以同时执行多个应用程序。
组成PVM的第二部分是PVM函数库。PVM以函数的形式与用户程序接口，向用户提供各种服务。用户程序需要通过函数调用来使用PVM的各种功能。下边我们简单介绍几类主要的PVM函数。
(1). 宿主语言. 我们称可以直接调用PVM函数的程序设计语言为宿主语言。PVM系统支持两种宿主语言，即FORTRAN和C语言。为了避免PVM函数与各节点机的函数库发生冲突，PVM的C语言函数皆以PVM_开头。PVM的FORTRAN语言函数名都以PVMF开头。
(2). 并行任务控制函数. 并行任务控制函数用来控制多任务的并行执行。第一组并行任务控制函数用于把用户进程转换为PVM任务，然后再转变成正常的进程。第二组并行任务控制函数用于返回系统中正在执行的任务的标识符，使应用程序能够辩认系统上正在运行的任务。PVM启动的所有任务都有一个任务标识符。任务标识符由PVMD提供，在系统中是唯一的。第三组并行任务控制函数用于启动和结束PVM任务。第四组并行任务控制函数用来实现动态任务组的控制。动态任务组机构是建立在PVM基础之上的。一个任务可以属于多个任务组。任务组在系统运行时可以动态地改变。动态任务组控制函数以组名为参数，包括建立和撤消任务组、向任务组添加任务、从任务组中删除任务等。一个任务组中的每个任务都可以查询组内其它任务的状态。
194
(3). 任务通信同步函数. PVM提供了两种任务间通信同步方式。一种是在任务之间发送信号。另一种是在任务之间进行消息传递。PVM提供了两组相应的通信同步函数。第一组通信同步函数用于在多任务之间发送信号，包括两种发送信号的函数。一种是发送UNIX信号。另一种是发送事件标志，包括任务的退出、网络节点机的删除与加入。应用程序可以调用PVM的相应函数检测到这些标志。PVM的第二组通信同步函数是消息传递函数，包括数据打包、数据拆包、数据包发送、数据包接收等函数。使用这组函数，任何任务都可以异步地向另一个任务发送消息，或者向一组任务广播消息。消息可以按照封锁(BLOCKING)或非封锁(NON-BLOCKING)方式来接收。接收函数可以按要求返回接收到的消息。消息缓冲区是动态分配的。所以，结点机上可用存储空间的大小决定了消息的长度。
(4). 虚拟并行机管理函数. 虚拟并行机管理函数提供动态改变PVM环境的功能。这类函数包括向系统加入结点机、从系统删除结点机、查询虚拟并行机配置信息等函数。
PVM除了具有上述功能外，还具有容错的特征。若组成系统的某台节点机发生故障，PVM能自动地检测出这台计算机并将其从系统删除。用户程序可以获得系统的状态信息。PVM不能自动地将非正常终止的任务恢复。所以，用户程序能否容错需由用户在编程时加以考虑。
美国Oak Ridge国家实验室和田纳西大学等单位在PVM的基础上开发了一个基于
X-WINDOWS窗口软件的机群并行计算环境。该环境是一个图形化的高级并行程序设计和运行环境。在这个环境下，用户只要用一种简单结构图描述程序的并行性和控制流，并用普通的程序设计语言设计基本的计算构件—子程序，系统就可以自动完成并行程序的设计、编译、调试和运行。
PVM已被用于多种计算任务，如分子学模拟、超导研究、矩阵计算等。由于PVM具有很高的I/O并行性，它可以有效地支持并行数据库系统。
2. EXPRESS并行软件环境
Express是最早出现的并行计算环境之一。它是ParaSoft公司于1988年推出的商品化系统。Express要求的硬件环境是一种“主机—结点机”结构。主机与结点机以及结点机之间的通信由消息传送机制通过高速连接网络实现，其拓朴结构可以是Mesh、Ring、Torus、Hypercube等。如果主机与节点机都是工作站(即工作站机群)，高速连接网可以由一般的局域网(如ETHERNET)替代。Express系统的主机和节点机有明确的分工。主机负责用户界面并完成I/O操作。节点机主要进行计算工作。
Express既可作为操作系统，也可以作为实用程序和库函数使用。当它运行在一个没有加载操作系统的并行计算机系统(如 Transputer阵列)上时，它就是一个操作系统，为并行程序提供多任务管理、I/O操作管理、调试跟踪等服务。当它在已加载操作系统的并行计算机系统(如工作站机群)上运行时，它就成为一种运行在操作系统之上的实用程序和库函数。Express由一组软件包组成。它以独立于具体机器结构的方式提供并行软件生存周期所要求的开发工具，包括分析、设计、编码、调试、性能评估、维护等工具，并为大多数工具提供了图形界面。
Express的目标是力图避免寻求新的或者复杂的方法去开发并行程序，而尽量采用接近于传统串行程序设计风格的规则来编写并行程序。这个目标使得Express类似于一种由传统程序设计方法简单扩展而成的并行程序开发环境。下边，我们简单介绍一下Express的功能和它提供的并行软件开发工具。
Express几个主要功能如下:
195
(1). 支持多个用户同时使用并行计算机系统。
(2). 在多种网络拓扑结构下实现透明的点对点通信。
(3). 提供管理控制多任务在多结点机上的并行运行，如建立、启动、终止任务等。
(4). 可以实现静态或动态的负载均衡调整策略。
(5). 实现用C或FORTRAN语言编写的顺序程序到并行程序的自动转换。
(6). 实现在高级语言级调试并行程序。
(7). 实现自动分析和评估并行程序的动态行为。
(8). 实现自动数据分解、在异构网络下运行并行程序等。
(9). 实现I/O共享，使各节点机能平等地访问主机，实现I/O操作。
Express有如下几个主要软件工具:
(1). Vtool:用于算法分析与设计的工具。它以动画方式显示算法的全过程，其中通过显示数据结构的引用和修改状况来演示算法的结构。
(2). Aspar: 用于编码阶段的工具。它能够把用C或FORTRAN语言编制的顺序程序转换为Express编程模式下的并行程序。Express编程模式包括数据划分、功能划分、客户/服务器等。Aspar还具有一个Ftool工具，用于分析程序中的变量引用和数据/控制流等静态结构。
(3). Ndb: 并行程序调试工具。Ndb的功能和调试命令与dbx相似。不同之处在于，它可以调试跟踪一组结点机上运行的并行程序。
(4). Ctool: 用于性能分析的工具。它通过实际运行并行程序来分析其用于计算、I/O和数据通信的开销，为用户进一步优化程序结构提供依据。
Express是一个商品化的系统。目前，它可以在下列并行计算机系统上运行:CRAY X-MP、CRAY Y-MP、CRAY-3D、CONVEX MPP、DEC ALPHA、DEC工作站机群、HP9000/800、HP工作站机群、Intel iPSC/i860、Intel iWarp、Intel Delta、Intel Paragon、IBM ES9000、IBM3090、IBM PVS、IBM RS/6000工作站机群、IBM SPI、Kendall Square KARI、nCUBE系列、SGI工作站机群、SUN工作站机群、CM5、Transputer系统等。
9.5 并行算法及其复杂性分析
并行算法是为并行计算机系统设计的算法。并行算法一般都是指可在SIMD计算机或MIMD计算机上执行的算法。可在SIMD计算机上执行的算法称为同步并行算法。可在MIMD计算机上执行的算法称为异步并行算法。在松散耦合的MIMD计算机上执行的算法也称为分布式并行算法。下面，我们讨论各类并行算法的复杂性分析方法。
并行算法的复杂性分析与顺序算法的复杂性分析有很大差别，需要考虑的因素很多。并行算法的复杂性测度包括工作量、运行时间、处理机数目、加速比、效率、伸缩性等。在并行算法的设计与分析中，我们必须全面考虑这些复杂性测度。
在分析算法的复杂性时，我们经常要考虑平均复杂性和最坏复杂性。设S、S、...、S是12k算法A的所有大小为N的输入，P是S的出现的概率，COMPLEXITY(S)是算法A在输入S上执iiii
196
行的复杂性，COMPLEXITY可以是工作量、执行时间等复杂性测度。A在大小为N的输入上的平均复杂性定义为
k。 ，，ACOMPLEXITYN,，COMPLEXITY(),SPiii,1
显然，分析算法的平均复杂性时，需要了解输入的分布情况，比较困难。最坏复杂性要比平均复杂性容易分析。最坏复杂性定义为
。 ，，,,WCOMPLEXITYN,MAXCOMPLEXITY() | 1,i,kSi
9.5.1. 并行执行时间
一个并行算法的并行执行时间是指它在并行计算机上求解一个输入大小为N的问题所需要的时间，记作RT(N)。设A是一个并行算法，P是处理器个数，t是执行A时第一个被启动的处理s
器开始运行的时间，t是最后一个停止运行的处理器的停止时间。算法A的并行执行时间是N和t
P的函数RT(N,P)=t- t。当并行算法是同步算法时，所有处理器的开始运行时间都是相同的，所ts
有处理器的终止时间也都是相同的。
算法分析工作一般在算法执行之前就要进行。人们通常使用算法执行的基本操作数近似地表示RT(N,P)。对于不同的计算模型，基本操作的定义也不相同。但是，无论对哪种计算模型来说，基本操作都仅需要常数执行时间。由于并行算法的执行时间RT(N,P)包括计算时间、I/O时间、通信时间三部分，我们估计一个并行算法的RT(N,P)时首先要计算这个算法需要执行的基本计算操作数、基本I/O操作数、基本通信操作数，然后考虑这三类操作是否并行运行，估计三类操作所需要的时间，最后使用加法或max求出RT(N,P)的估计式。
9.5.2. 工作量
一个并行算法的工作量定义为该算法执行时所使用的处理器数量和并行执行时间的乘积。我们用Cost(N)表示一个并行算法求解一个输入大小为N的问题时的工作量,则
Cost(N)=P×RT(N,P)，
其中P是处理器数量。Cost(N)是求解输入大小为N的问题时所有处理器运行时间总和的近似值。一个MIMD机器求解一个问题的工作量可能会小于Cost(N)，因为RT(N,P)是所有处理器中运行时间最长的处理器的运行时间。换言之，Cost(N)是在假定每个处理器的运行时间皆相等的条件下的并行算法的工作量。我们希望最快顺序算法的运行时间与Cost(N)之比越大越好，理想值是1。
9.5.3. 加速比
197
设A是求解问题P的最快顺序算法，PA是求解问题P的一个并行算法，A的运行时间是RT(N)，PA的运行时间是RT(N,P)。并行算法PA加速比定义为: APA
S(N,P)=RT(N)/RT(N,P)。 APA
很多问题的最快顺序算法还不清楚。所以我们一般都是使用已知最快顺序算法的执行时间来计算并行算法的加速比。显然，S(N,P)越大，并行算法越好。S(N,P)的理想值是P，但实际上是达不到的，因为并行算法运行时需要很多额外开额，如通信同步等。事实上，由于任一并行算法皆可在一台串行机上模拟，所以RT(N)P×RT(N,P)，于是S(N,P)P。 ,,APA
9.5.4. 效率
一个具有高加速比的并行算法对处理器的利用率可能很低。S(N,P)不能全面反映并行算法
的性能。为此，我们需要另一个并行算法的复杂性测度，即效率。并行算法的效率定义为:E(N,P)=S(N,P)/P。E(N,P)是度量并行算法的处理器利用率的测度。由S(N,P)P可知，,0。 12n
'''''',s,s,....,s,s,s,....,s 输出:， nn1212
*使用n个处理机完成n个数的排序。
?算法
199
? FOR i=1 TO n 并行地Do
? p从左邻接点接收一个数据; i
? p把输入数与存储的数进行比较; i
? p输出大值到右邻接结点; i
? p存储小值到p的局部存储器; ii
? 输出排序的数列:任一个处理机无左输入，则开始向左传输数据。
?例子
30512
3051 2
305 2 1
30 5 1 2
3 1 2 0 5
3 5 0 1 2
3 5 0 1 2
3 0 1 2 5
5 0 1 2 3
0 1 2 3 5
?复杂性分析:
200
响应时间:T=2n-1(sort) T=n(output) T(n)=T+T=,(n) 1212
使用的处理机数:P(n)=n
加速性:S(n)=,/T(n)=,(n,logn)/,(n)=,(logn)
2 工作量:W(n)=T,P=,(n),n=,(n)
有效性:E(n)=S(n)/n=,(logn)/n=,(logn/n)
2. 用少于N个处理机排序N个数
?可行性条件
用P个Processors排序n个数，每个Processor必须能够存储n/P个数。
?方法
一般算法:设A是用于具有P个处理机的并行计算机的算法，G是一个具有P个处理机1122
，，p的并行计算机，PP个处理机上设计的有效算法可以转换为P个处理机上的有效算法。 122
2. 若P=1,有效并行算法可以转换为有效顺序算法。 2
* 顺序算法转为有效并行算法是open problem!
9.6.2 线形数组并行机上的奇—偶交换算法
1. 奇—偶交换方法
?问题定义
输入:S=，S存储与P中n个存储机。 12nii
'''s,s,....,s 输出:s’存储与P中， iin12
?算法
设s在P中 ii
201
基本思想:设S={6,5,9,2,4,3,5,1}，
奇数步:比较交换(6,5)，(9,2)，(4,3)，(5,1), 得
S={5,6,2,9,3,4,1,5}
偶数步:比较交换(6,2)，(9,3)，(4,1), 得
S={5,2,6,3,9,1,4,5}
如此继续下去循环次数:，n/2，次，得到S={1,2,3,4,5,5,6,9}
DO 算法:FOR j=1 TO ，n/2，
FOR i=1, 3, …., 2，n/2，-1 Do in parallel
IF s>s THEN s,s; ii+1ii+1
ENDFOR;
FOR i=2, 4, …., 2，(n-1)/2， DO in parallel
IF s>s THEN s,s; iI+1ii+1
ENDFOR;
ENDFOR
例:S={6,5,9,2,4,3,5,1}
516 5 9 2 4 3
?复杂性分析
响应时间:T(n)=O(n)
处理机数:P=n
2 工作量: W(n)=P,T(n)=O(n)
加速性: S(n)=,/T(n)=,(nlogn)/O(n)=O(logn)
有效性: E(n)=S(n)/P=O(logn)/O(n)=O(logn/n)
2. 一般化的奇—偶交换方法
?问题
输入:S=， 12n
处理机数N，Nj，则s在s之后 ijij
S={5,2,4,5}, (p,….., p)计算与s对应的C 例: 令i1inii
S p pppC S 1112 13 14
5 5/5 5/2 5/4 5/5 2 2
P ppp 2122 23 24
2 2/5 2/2 2/4 2/5 0 4
P ppp 3132 33 34
4 4/5 4/2 4/4 4/5 1 5
P ppp 4142 43 44
5 5/5 5/2 5/4 5/5 2 5
算法
(1) FOR i=1 To n Do in parallel
(2) FOR j=1 To n Do in parallel
(3) If (s>s) OR (s=s and i>j) ijij
(4) then P(i,j)在C中写1 i
(5) else P(i,j)在C中写0 i
(6) ENDFOR
(7) FOR i=1 To n Do in parallel
(8) P(i,1) 存S中写到S`(c+1) ii
(9) ENDFOR
4. 复杂性分析
响应时间:(1)—(6)要求O(1)时间
(7)—(8)要求O(1)时间
T(n)=O(1)
205
2 处理机数:P=n
2工作量: W(n)=T(n).P=O(n)
加速性: S(n)=O(nlogn)/O(1)=O(nlogn)
2有效性: E(n)=S(n)/P=O(nlogn)/O(n)=O(logn/n)
E(n) ,0 *有效性很低，n,,，
5. 注释
?该方法依赖于:
(1) CRCW
(3) 非常多的处理器
模型太强了，无实际意义。
?可以用n处理器实现该算法。
9.6.4 CREW并行计算机上的Merge算法
1. 计算模型
SIMD、CREW、Shared-Memory、N procesors
2. 问题定义
a,a,....,a 输入:A=，， 12r12r
b,b,....,b B=，, r,s, 12ss12
处理器数N，N,r
输出:C=,A,B;c,c,….,c12r+s12r+s
3. 算法
基本思想:
(1) 每个处理器可运行两个过程
SEQUENTIAL MERGE /* O(n) */
BINARY SEARCH /* O(logN) */
(2) 例:N=4，r=s=12
A={2,3,4,6,11,12,13,15,16,20,22,24}
B={1,5,7,8,9,10,14,17,18,19,21,23}
? 把A和B分为相等大小的N个子序列:
A: <2,3,4> <6, 11, 12> <13,15,16> <20,22,24>
A’: 4 12 16 /* A’[i]=A[i*(r/N)] */
B: <1,5,7> <8, 9, 10> <14,17,18> <19,21,23>
B’: 7 10 18 /* B’[i]=B[i*(s/N)] */
206
? 合并A`和B`形成一个三元组序列:
V=<(4,1,A), (7,1,B), (10,2,B), (12,2,A},(16,3,A),(18,3,B)>
*第一分量表示数，第二分量表示数在A’或B’中的位置，第三分量表示数所在数组。 ? 确定每个处理机需要Merge的两个A与B的子集的第一个元素送数组Q，Q(i)=(x,y)
表示第i个处理机合并由位置x开始的A子列和由位置y开始的B子列:Q(1)=(1,1)，
Q(2)=(5,3), Q(3)=(6,7), Q(4)=(10,9)_
P根据Q(i)=(x,y)，合并由位置x开始和由位置y开始的A和B的子序列，送到由x+y-1 ? i
开始的C的子列.
算法
? FOR i=1 To N-1 Do in parallel
P确定A’[i]和B’[i]: A’[i]?A[i，r/N，];B’[i]?B[i，s/N，]; i
? FOR i=1 To N-1 Do in parallel
P用二元查找法在B’中找满足A’[i]1 Do
(2.1) FOR m=1 to ，v/2， Do in parallel
u+1uuP,P,P m2m-12mu+1uuu+1用P中的处理器完成CREW—MERGE(S, S, S) m2m-12mmu+1uu+1u (2.2) If v是奇数 THEN P, P;S, S; ，v/2，v，v/2，v
(2.3) u,u+1;v?，v/2，
ENDwhile
4. 复杂性分析
响应时间:step1: O(n/N log(n/N))
208
step2: O(，logN， (n/N+logn))
2 T(n)=O(n/Nlogn+logn)
处理机数:P=N
2 工作量: W(n)=O(nlogn+N logn)
2 加速比: S(n)=,/T(n)=O(nlogn)/O(n/Nlogn+logn)=O(1/(1/N+logn/n))
n,,，S(n)=N
N,,，S(n)=n/logn
有效性: E(n)=O(1/(1+N/nlogn))
E(n) ,1 n,,，
N,,，E(n) ,0
9.6.6 EREW并行计算机上的排序算法
9.6.6.1. 计算模型
?SIMD、SM、EREW
?EREW要求必须避免写和读冲突，需要三个算法
EREW—Broadcasting算法
All—sums算法
EREW—Selection算法
9.6.6.2. Broadcasting算法
1. 问题定义
输入:D=存储器中的一个单元，N个处理器。
输出:D的数据输送到所有N个处理器。
2. 算法
基本思想:
D 1 2 3 4 5 6 7 8
,数组A N=8 5 5
5 Step 0
pppppppp1 2 3 4 5 6 7 8
209
1 2 3 4 5 6 7 8
5 5
5 5 Step 1
pppppppp1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
5 5 5 5
Step 2 logN
5 5 5 5
pppppppp 1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
5 5 5 5 5 5 5 5
Step 3
5 5 5 5 5 5 5 5
pppppppp1 2 3 4 5 6 7 8
算法:
Step 1:Processor p执行:1
读D的值;
存储到自己的存储器;
写入A(1);
Step 2:FOR i=0 To (logN-1) Do
ii+1 FOR j=2+1 To 2Do in parallel
Processor P执行:j i 读A(j-2)的值;
存储到自己的存储器;
写入A(j);
ENDFOR;
ENDFOR.
3. 复杂性分析:
响应时间:T=O(logN)
210
处理机数:P=N
工作量: W=T,P=O(NlogN)
9.6.6.3 Prefix sums算法
1. 问题定义
输入:处理P存储有a，1,I,N II
输出:P中存储a+a+….+ a，1,I,N i12I
2. 算法
基本思想:设A= a+a+….+ a， ijII+1j
例:N=8
pppppppp1 2 3 4 5 6 7 8
aaaaaaaa1 2 3 4 5 6 7 8
step 1 AAAAAAAA11 12 2334 45 56 67 78
3
step 2
AAAAAAAA11 12 14 25 36 47 50 13 logN
step 3 AAAAAAAA11 12 1314 15 16 17 18
算法:
FOR j=0 To logN-1 Do
j+1 FOR I=2 To N Do in parallel
Processor pI
jj+1jj(2-1)j (i) 从p得到a/*I-2=2-2=2=2*/ jjI-2I-2
(ii) a+a代替a IIjI-2
ENDFOR
211
ENDFOR
3. 复杂性分析
响应时间:T=logN
处理机数:P=N
工作量: W=O(NlogN)
Select算法 9.6.6.4 EREW—
1. 问题定义
输入:S={s,s,…s}，1,k,n 12n
输出:S的第k个最小数
1-x处理机数:N=n，0m把S分为三个子序列
(5) 最后递归地完成选择S中第k个最小值
例 S={18, 35, 21, 24, 29, 13, 33, 17, 31, 27, 15, 28,
11, 22, 19, 25, 34, 32, 16, 12, 23, 30, 26, 14, 20}
|S|=n=25, N=5, k=6.
1-x1-xx0.51-x 由N=5=n=25可以求出x=0.5, n=25=5, n=5.
下边给出了求S中第6个最小数的过程:
Step (1) 的结果:
S={18, 35, 21, 24, 29} S={13, 33, 17, 31, 27} S={15, 28, 11, 22, 19} 123
S={25, 34, 32, 16, 12} S={23, 30, 26, 14, 20} 45
Step (2) 的结果:
M={24, 27, 19, 25, 23}
Step (3) 的结果:
m=24
Step (4) 的结果:
L={18, 21, 13, 17, 15, 11, 22, 19, 16, 12, 23, 14, 20} /* S的低部 */
212
E={24}
G={35, 29, 33, 31, 27, 28, 25, 34, 32, 30, 26} /* S的高部 */
递归 处理L，因为|L|>6.
算法:
PABALLEL-Select(S, k)
Step 1:
IF n,4 THEN P使用常数次比较返回第k个最小元素 1
ELSE
x1-x(i) S分为等长(n)的n子序列S、….、S 1i
(ii) S分配到P ii
ENDIF
Step 2:
1-x FOR i=1 To n Do in parallel
处理机P,/2，)，结果存储到M[i] 执行Sequential-select(S, ，,Siii
ENDFOR
Step 3: m=PABALLEL-Select(M, ，,M,/2，)
Step 4:
划分S为三个子序列
L={s,S | s m} ii
Step 5:
If ,L,,k THEN PARACLEL-SELECT(L, k)
Else If ,L,+,E,,k THEN return m
Else Parallel-select(G, k-,L,-,E,)
Endif
Endif
3. 复杂性分析
响应时间:设T(n)是响应时间;
Step 1:用Broadcast算法向所有处理机传送S的开始地址、,S,和k，需
1-x 要O(log(n))时间;
1-x P计算S的开始和结束地址(for i=1 to n), 需要O(1)时间。 iixx Step 2:在长度为n的S中找中间值，需O(n)时间 i1-x1-x Step 3: 需要T(n), 因,M,=n
1-x1-x Step 4: (i) m被Broadcust传递到n个处理机, 需O(n)时间
xx (ii) 每个P划分S为L、E、G, 需要O(n)时间，因为|S|=n. iiiiii
(iii) L, E,G,合并为L, E, G; ii i
213
令a=,L,，z=0，L的合并如下(同法可合并E、G): ii0iii
i1-x? FOR i=1 To n 计算z= (使用prefix-sums算ai,jj,1
)， 法
1-x 需要O(log n)
x? P把L送入L，起始位置为z+1，需要O(n)时间. iii-1
x 于是总时间要求为O(n)。
1-x,L,,3n/4，,G,,3n/4。因为m是M的中间值，M中至少有n/2个 Step 5:
x 值大于m;M的每个元素都是某个S的中间值，故至少有S的n/2 i1-xx 元素大于M的每个中间值，于是,L,,n- (n/2), (n/2)=3n/4. Step 5要求
T(3n/4)时间.
x1-xxx于是，T(n)=O(logn)+O(n)+T(n)+T(3n/4),O(n+t(3n/4))=O(n)(用展开法)
1-x 处理机数:P(n)=n
1-xx工作量: W(n)= n,O(n)=O(n)
x1-x 加速性: S(n)=O(n)/O(n)=O(n),O(n/logn)
1-x1-x 有效性: E(n)=O(n)/ n =O(1)
9.6.6.5 EREW—SORT算法
1. 问题定义
1-x 输入:S=，N= n处理机 12n
'''s,s,....,s输出: n12
2. 算法
基本思想:
1/x1/x1/x(1) 取2-1个点，把S分为2个子序列 (每个序列长为n/2):
(1/x)-1 S, S, …., S, S, S, (j=2) S‖, ― S‖, ―…. ‖, ― S 12jj+12j1 2 2j(2) 并行递归地排序S、S、….、S, 每个子序列用N/j个处理器。 12j
，1/x，1-x，1/x， 算法:令k=2，N=n，x满足:，1/x，,10，n,2，
EREW-Sort(S)
(1) IF n,k Then Quicksort(s); (2) ELSE FOR i=1 To k-1 Do (3) PARALLEL-SELECT(S, ，i，n/k，)
(4) ENDFOR
(5) S,{s,S | s,m} 11
214
(6) FOR i=2 To k-1 DO
(7) S,{s,S | m,s,m} ii-1i
(8) ENDFOR
(9) S,{s,S | s,m} kk-1
(10) FOR i=1 To k/2 Do in parallel
/* 并行排序S….、S, 每个子序列用N/j个处理器 */ 1j
(11) EREW-Sort(S) i
(12) ENDFOR
(13) FOR i=(k/2)+1 To k Do in parallel
/* 并行排序S….、S, 每个子序列用N/j个处理器 */ j+1k
(14) EREW-Sort(S); i
(15) ENDFOR
(16) ENDIF
3. 复杂性分析
xx应时间:(2)-(4):kO(n)=O(n) 响
(5)-(9):由于Parallel-Select已把S分为k个子序列，且S中元素皆在m与mii-1I
之间，故只需计算出S的起始与终止地址，故需O(k)时间 i
(10)-(11):t(n/k), 因,S,=n/k i
(13)-(14):t(n/k)
xx T(n)=O(n)+2t(n/k)=O(nlogn) (展开法)
1-x处理机数:P(n)=n
1-xx工作量: W(n)=O(nnlogn)=O(nlogn)
xx加速性: S(n)=nlogn/nlogn=n/n0 then k,k endif ii
Endfor
5. 复杂性分析
(1)EREW模型
step 1:使用Broadcast—O(logN)
O(n/N) step 2:Seqential-search—
step 3:使用store—O(logN)
于是:T(n)=O(logN)+O(n/N) W(n)=O(NlogN+n)
(2) ERCW
step 1:使用Broadcast—O(logN)
step 2:Seqential-search—O(n/N)
step 3:O(1)
T(n)=O(logN+n/N) W(n)=O(NlogN+n)
(3) CREW
step 1:O(1)
step 2:O(n/N)
step 3:O(logN)
T(n)=O(logN+n/N) W(n)=O(NlogN+n)
(4)CRCW
step 1:O(1)
step 2:O(n/N)
step 3:O(1)
T(n)=O(n/N) W(n)=O(n)
(5)令N=n，查询q个x，对于EREW、ERCW、CREW:T(n)=O(qlogn)
对于CRCW:T(n)=O(q,N/N)=O(1)
5.2.2. Searching on a Tree
1. 计算模型:具有n个叶的Tree-connected SIMD 计算机
224
叶结点:存储S—被search的数据集合
(1)接入输入 Root:
(2)向两个子结点传输，从接收的输入
(3)从两个子结点接收，输出
(4)产生输出
中间结点:(1)从父结点接受一个输入
(2)传输输入到子结点
(3)从两个子结点接收输入
(4)组合 子结点的输入
(5)传送组合结果到父结点
以下讨论 Quering
1. 问题定义:输入:S={s,s,….,s}存储于叶x 12n
输出:yer如果x在S中 no如果x不在S中 2. 基本算法:
(1) Root 读x
FOR i=0 To logn-1 Do
iFOR j=1 To 2 Do in Parallel
i级第j个结点向其两个子结点传送x
(2) FOR i=1 To n Do in Parallel
第i叶结点做
IF x=s THEN 向上输出1 i
ELSE 向上输出0
(3) FOR i=logn-1 DOW—to 0 DO
i FOR j=1 To 2 Do in Parallel
i级显示结点接收其两个子结点传送的值r,r; 23. 复杂性:T(n)=O(logn)
W(n)=O(Nlogn) 4. q个查询的流水形式并行处理
复杂性:(1)产生第一个回应需要O(logn)时间
(2)以后每步产生一个新回应
(3)第一个回应产生后，q-1单位时间内产生所有回应
T(n)=O(logn)+O(q)
W(n)=O(Nlogn)+O(Nq)=O(nlogn)+O(nq)
225
5.2.3. Searching on a Mesh 1. 计算模型:SIMD、Mesh-connected，图5.8 p129
特点:(1)任意两个处理器间连线长度为常数
(2)区域是O(n)
问题:p接收输入，产生输出。 2.111/21/2 输入:S={s,….s}，s在p中，x 11nnijij
输出:yes--x,S no--x,S
3. 算法:基本思想:使用二维数组B={b} ij
，传递到所有p(i,j);若p(i,j)中数=x，则置b=1 (1) 第一阶段:p(1,1)读xij
(2) 第二阶段:回送各处理器的比较结果，由p产生回答。 11
例:pp Fig.5.9 (3)
算法:pp 129
4. 复杂性分析:T(n):step 1=O(1)
1/21/2step 2=O(n):n-1步传送信息
1/21/2-1步传送信息 step 3=O(n) n
step 4=O(1)
1/2 T(n)=O(n)
1/23/2 W(n)=O(n,n)=O(n)
1/21/2 S(n)=O(n/n)=n
3/21/2 E(n)=O(n/n)=O(1/n)
226
227
浙公网安备 33021202002483