计算机算法基础主讲：刘芳华中科技大学计算机学院算法的研究内容
问题是否可解
1930’s 研究集中于判断特定问题在计算机上是否可解，基本方法为：选定一个计算模型，观察是否能在该模型上创建能解决问题的算法。这些计算模型包括,Post machines,Turing machines等。这一阶段的成果是,大部分问题为不可解 。
高效率的解决方法
随着计算机的发展和数据资源的增加，算法研究转向针对可解的问题，找到高效率的解决方法。
算法的应用
数据库中的检索
搜索引擎中的爬找器和检索
公共密钥加密和数字签名技术
优化问题
最短路径
资源分配
…
章节安排
,计算机算法基础,,余祥宣、崔国华、邹海明著，华中科技大学出版社
第一章 导引与基本数据结构 √
第二章 分治法 √
第三章 贪心方法 √
第四章 动态规划 √
第五章 检索与周游 √
第六章 回溯法 √
第七章 分枝 -限界 √
第八章 NP-问题 ⊙
预备知识
数学：集合、证明方法（直接、间接、反证、
反例、归纳假设）、对数基础、
FLOOR&CEILING函数、阶乘、递归关系
数据结构：链接表、图、树、二元树第一章 导引与基本数据结构
1.1 算法的定义及特性
1,什么是算法？
算法是解一 确定类问题 的任意一种 特殊的方法 。
在计算机科学中，算法是使用计算机解 一类问题 的精确、有效方法的代名词：
算法 是一组 有穷的规则,它规定了解决某一 特定类型问题 的一系列 运算 。
2,算法的五个重要特性确定性,能行性,输入,输出,有穷性
1） 确定性,算法的每种运算必须要有确切的定义，不能有二义性。
例：不符合确定性的运算
5/0
将 6或 7与 x相加
未赋值变量参与运算
2） 能行性算法中有待实现的运算都是基本的运算，
原理上每种运算都能由人用纸和笔在有限的时间内完成。
例：整数的算术运算是“能行”的实数的算术运算是,不能行” 的
3） 输入每个算法有 0个或 多 个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合 ——定义域 （或值域）
4） 输出一个算法产生 一个 或 多个 输出，这些输出是同输入有某种特定关系的量。
5） 有穷性一个算法总是在执行了 有穷步 的运算之后 终止 。
计算过程,只满足确定性、能行性、输入、输出四个特性但 不一定能终止 的一组规则。
准确理解算法和计算过程的区别：
不能终止的计算过程：操作系统
算法是“可以终止的计算过程”
算法的时效性：只能把在 相当 有穷步内终止的算法投入到计算机上运行
3,我们的主要任务算法学习将涉及 5个方面的内容：
1） 设计算法,创造性的活动
2） 表示算法,思想的表示形式
3） 确认算法,证明算法的正确性程序的证明
4） 分析算法,算法时空特性分析
5） 测试程序,调试和作出时空分布图本课程集中于学习算法的 设计 与 分析 。通过学习，掌握计算机算法设计和分析 基本策略与方法,
为设计更复杂、更有效的算法奠定基础
1.2 分析算法
1,分析算法的目的在于：通过对算法的分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物力浪费。
算法分析是计算机领域的古老而前沿的课题。
进行算法分析的基本技术：抽象
2,重要的假设和约定
1）计算机模型的假设
Turing机模型：计算机形式理论模型
通用计算机模型：
单处理器
有足够的“内存”
能在固定的时间内存取数据单元
2）计算的约定
确定使用什么样的运算及其执行时间。
从计算时间上，运算的分类：
时间囿界于常数的运算,尽管每种运算的执行时间不同，但一般只花 一个 固定量 的时间（单位时间）
就可完成。
· 基本算术运算，如整数、浮点数的加、减、乘、除
· 字符运算
· 赋值 运算
· 过程调用等
2）计算的约定（续）
其他运算,
· 字符串操作：与字符串中字符的数量成正比
· 记录操作：与记录的属性数、属性类型等有关
· 特点：运算时间 无定量如何分析非时间囿界于常数的运算：分解成若干时间囿界于常数的运算。
如,Tstring = Length（ String） * tchar
算法的执行时间 =∑Fi*ti
其中,Fi是算法中用到的某种运算 i的次数,ti是该运算执行一次所用的时间。
3）工作数据集的选择
编制能够反映算法在最好、平均、最坏情况下工作的 数据配置 。然后使用这些数据配置运行算法，
以了解算法的性能。
测试数据集的生成
作为算法分析的数据集：典型特征
作为程序性能测试的数据集：对执行指标产生影响的性质
3,如何进行算法分析？
对算法进行全面分析，可分两个阶段进行：
事前分析,就算法本身，通过对其执行性能的理论分析，
得出关于算法特性 ——时间和空间 的一个特征函数（ Ο,Ω） ——与计算机物理软硬件没有直接关系。
事后测试,将算法编制成程序后实际放到计算机上运行，
收集其执行时间和空间占用等统计资料，进行分析判断 ——直接与物理实现有关。
1）事前分析
目的：试图得出关于算法执行特性的一种形式描述，以“理论上”衡量算法的“好坏”。
如何给出反映算法执行特性的描述？
最直接方法,统计算法中各种运算的执行情况，包括：
运用了哪些运算
每种运算被执行的次数
该种运算执行一次所花费的时间等。
算法的执行时间 =∑Fi*ti
频率计数例：
x←x+y for i ←1 to n do for i ←1 to n do
x ← x + y for j ←1 to n do
repeat x ← x +y
repeat
repeat
(a) (b) (c)
分析：
(a),x←x+y 执行了 1次
(b),x←x+y 执行了 n次
(c),x←x+y 执行了 n2次定义：
频率计数,一条 语句 或一种 运算 在算法（或程序）体中的执行次数。
算法 2.7 插入分类
procedure INSERTIONSORT(A,n)
//将 A(1,n)中的元素按非降次序分类,n≥1//
1 A(0)← -∞//设置初始边界值
2 for j←2 to n do //A(1:j -1)已分类 //
3 item←A(j);i←j -1
4 while item<A(i) do //0≤i<j//
5 A(i+1)←A(i); i←i -1
6 repeat
7 A(i+1) ←item;
8 repeat
end INSERTIONSORT
(8,5,4,9)
(8,5,4,9)
(5,8,4,9)
(5,8,4,9)
(4,5,8,9)
(4,5,8,9)
一条语句在整个程序运行时实际执行时间 =
频率计数 * 每执行一次该语句所需的时间
如何刻画算法执行特性的形式描述
实际执行时间受约于诸多实际因素，如机器类型、编程与语言、操作系统等，没有统一的描述模型。
在事前分析中，只限于确定与所使用的机器及其他环境因素无关的频率计数，依此建立理论分析模型。
数量级
语句的数量级,语句的执行频率例,1,n,n2
算法的数量级,算法所包含的所有语句的执行频率之和。
算法的数量级从本质上反映了一个算法的执行特性。
例：假如求解同一个问题的三个算法分别具有 n,n2,n3数量级。
若 n=10，则可能的执行时间将分别是 10,100,1000个单位时间 ——与环境因素无关。
计算时间 /频率计数的表示函数通过事前分析给出算法计算时间（频率计数）的一个 函数 表示形式，一般记为与 输入规模
n有关的函数形式,f(n)
注：最高次项与函数整体的关系
空间特性分析（略）
2）事后测试
目的：运行程序，确定程序实际耗费的时间与空间，验证先前的分析结论 ——包括正确性、执行性能等，比较、优化所设计的算法。
分析手段：作时、空性能分布图
4,计算时间的渐近表示记：算法的计算时间为 f(n)
数量级限界函数为 g(n)
其中，
n是输入或输出规模的某种测度。
f(n)表示算法的“实际”执行时间 —与机器及语言有关 。
g(n)是 形式简单 的函数，如 nm,logn,2n,n!等。是事前分析中通过对计算时间或频率计数统计分析所得的,与机器及语言无关 的函数。
以下给出算法执行时间,上界 （ О）,下界 （ Ω ）、
“平均” （ ）的定义。
1）上界函数定义 1 如果存在两个正常数 c和 n0，对于所有的 n≥n 0，有
|f(n)| ≤ c|g(n)|
则记作 f(n) = Ο(g(n))
含义：
如果算法用 n值不变的同一类数据在某台机器上运行时，所用的时间总是小于 |g(n)|的一个常数倍。所以 g(n)是计算时间 f(n)的一个 上界函数 。 f(n)的数量级就是 g(n)。
试图求出 最小 的 g(n)，使得 f(n) = Ο(g(n))。
多项式定理,
定理 1 若 A(n) = amnm+?+a 1n+a0是一个 m次多项式，则有 A(n) = Ο(nm)
即：变量 n的固定阶数为 m的任一多项式，与此多项式的最高阶 nm同阶。
证明：取 n0=1,当 n≥n 0时，有
|A(n)|≤|am|nm+…+|a 1|n+|a0|
≤(|am|+|am-1|/n+…+|a 0|/nm) nm
≤(|am|+|am-1|+…+|a 0|) nm
令 c= |am|+|am-1|+…+|a 0|
则，定理得证。
计算时间的数量级对算法有效性的影响数量级 的大小对算法的有效性有 决定性 的影响。
例：假设解决同一个问题的两个算法，它们都有 n个输入，计算时间的数量级分别是 n2和 nlogn。则，
n=1024：分别需要 1048576和 10240次运算。
n=2048：分别需要 4194304和 22528次运算。
分析：在 n加倍的情况下，一个 Ο(n2)的算法计算时间增长 4
倍，而一个 Ο(nlogn)算法则只用 两 倍多一点的时间即可完成。
算法 2.8 归并分类
procedure MERGESORT(low,high)
//A(low:high)是一个全程数组，它含有 high-low+1≥0 个待分类的元素 //
integer low,high
if low<high then
mid← //计算 中分点 //
call MERGESORT(low,mid) //在第一个子集合上分类 (递归 )//
call MERGESORT(mid+1,high) //在第二个子集合上分类 (递归 )//
call MERGE(low,mid,high) //归并已分类的两子集合 //
endif
end MERGESORT
h ig h )/ 2(lo w?
Merge算法示例
(4,5,8,9)|(1,2,6,7)? (1,2,4,5,6,7,8,9)
参数,low = 1; high = 8; mid = 4
(4,5,8,9)|( 1,2,6,7)
h j j j jh h
(1 42 5 6 7 8 9)
j
算法分类（计算时间）
多项式时间算法：可用多项式（函数）对其计算时间限界的算法。
常见的多项式限界函数有：
Ο(1) < Ο(logn) < Ο(n) < Ο(nlogn) < Ο(n2) < Ο(n3)
指数时间算法：计算时间用指数函数限界的算法常见的指数时间限界函数：
Ο(2n) < Ο(n！ ) < Ο(nn)
说明：当 n取值较大时，指数时间算法和多项式时间算法在计算时间上非常悬殊。
典型的计算时间函数曲线
当数据集的规模很大时，要在现有的计算机系统上运行具有比 Ο(nlogn)复杂度还高的算法是比较困难的。
指数时间算法只有在 n取值 非常小时 才实用。
要想在顺序处理机上扩大所处理问题的规模，有效的途径是 降低算法的计算复杂度,而不是（仅仅依靠）提高计算机的速度。
计算时间函数值比较定义 1.2 如果存在两个正常数 c和 n0，对于所有的 n≥n 0，
有
|f(n)| ≥ c|g(n)|
则记作 f(n) = Ω(g(n))
含义：
如果算法用 n值不变的同一类数据在某台机器上运行时，所用的时间总是不小于 |g(n)|的一个常数倍。所以 g(n)是计算时间 f(n)的一个下 界函数 。
试图求出,最大,的 g(n)，使得 f(n) = Ω(g(n))。
2）下界函数定义 1.3 如果存在正常数 c1,c2和 n0，对于所有的 n≥n 0，
有
c1|g(n)| ≤|f(n)| ≤ c 2|g(n)|
则记作含义：
算法在最好和最坏情况下的计算时间就一个常数因子范围内而言是相同的。可看作：
既有 f(n) = Ω(g(n))，又有 f(n) = Ο(g(n))
))(()( ngnf
3）“平均情况”限界函数
4）限界函数的性质
1）若 且,则 。即 О具有传递性。（ 同）
2） 当且仅当
3）若,则 。即,定义了一个等价关系（等价类）
)(gf )(hg )(hf
、
)(gf )( fg
)(gf )( fg
5,常用的整数求和公式在算法分析中，在统计语句的频率时，求和公式的一般表示形式为：
如：
h ( n )i)(
)(
ng
if
)( 1
1
k
ni
k ni
1+1+…+1 （有 n项 1） = n
1+2+…+n = n 2
12+ 22 +…+ n 2 = n3
20+ 21 +…+ 2 n = 2n+1?
1.3 关于 SPARKS语言
本书为描述算法选用的一种类计算机语言
类 PASCAL语言
结构化程序描述
1,基本语法成分
1）数据类型：整型、实型、布尔型、字符型
2）变量声明,integer i,j; boolean b; char c
3）赋值运算,（变量） ← （表达式）
4）逻辑运算,and or not
5）关系运算：＜ ≤ ＝ ≠ ≥ ＞
6）变量声明：类型说明符 变量；
7）数组声明,integer A（ 1,5,7,20）
8）控制结构：
顺序,
分支,
· if condition then S1
else S2
endif
· case
:cond1:S1;
:cond2:S2;
…
:condn:Sn
:else:Sn+1
endcase
循环,
· while cond do
S
repeat
· loop
S
until cond repeat
· for vble←start to finish by increment do
S
repeat
2,同质异项
3,其它函数的定义与调用、函数和过程、变量与形式参数
1.4 基本数据结构
1,栈和队列
栈和队列,n个元素的线性表
利用动态数据结构 ——链表 实现栈或队列
利用静态数据结构 ——数组 实现栈或队列
基于以上两种表示形式的栈和队列上的基本运算队列的数组表示栈的数组表示用一维数组 STACKS（ 1:n）表示栈底,STACKS（ 1） 第 i个元素 STACKS(i)
栈顶指针,top
procedure ADD(item,STACAK,n,top)
if top ≥ n then call STACKFULL
endif
top← top +1
STACK(top) ← item
end add
procedure DELETE(item,STACK,top)
if top ≤ 0 then call STACKEMPTY
endif
item ← STACK(top)
top ← top-1
end DELETE
栈的数组表示 ——增加、删除栈的链接表表示一种单向链接表两个信息段,DATA存放数据,LINK指向前一节点节点插入
call GETNODE(T)
DATA(T) ←item
LINK(T) ←STACK
STACK ← T
节点删除
item ←DATA(STACK)
T ←STACK
STACK ←LINK(SATCK)
call RETNODE(T)
A
STACK
0
栈的链接表表示 ——增加、删除
2,树
1）树的一般定义定义 1.4 树（ tree） 是一个或多个结点的 有限 集合，它使得：
有一个指定为 根 （ root）的结点
剩余结点被划分成 m≥0 个不相交的集合：
T1,?,Tm
这些集合的每一个又都是一棵树，并称 T1,?,Tm为根的子树。
关于树的重要概念
结点的度 （ degree）：一个结点的子树数
树的度,树中结点度的最大值
结点的级 （ level）（又叫层）：设根是 1级，若某结点在 p级，则它的儿子在 p+1级
树的高度（或深度）,树中结点的最大级数
叶子（终端结点）,度为 0的结点
内结点（非终端结点）,度不为 0的结点
森林,m≥0 个不相交树的集合。
树的表示方法用 链接表 表示每个结点三个信息段：
TAG,DATA,LI
NK
TAG＝ 0，
DATA存数据；
TAG=1,DATA
存链接信息，
指向一棵子树
2）二元树定义 1.5 二元树 （ binary tree）是结点的有限集合，它或者为 空,或者由一个根和两棵称为左子树和右子树的不相交二元树所组成。
二元树与度为 2的树的区别
二元树性质 1：
引理 1.1 一棵二元树第 i级的最大结点数是 2i-1。深度为 k的二元树的最大结点数为 2k-1,k>0。
特殊形态的二元树
满二元树,深度为 k且有 2k-1个结点的二元树
完全二元树,一棵有 n个结点深度为 k的二元树，
当它的结点相当于深度为 k的满二元树中编号为 1到 n的结点时，称该二元树是完全的。
完全二元树的叶子结点至多出现在相邻的两级上。
完全二元树的结点可以紧凑地存放在一个一维数组中（性质见引理 1.2）。
二元树的表示方法
1.数组表示法：对于完全二元树，空间效率好；其他二元树，要浪费大量空间
2.链表法：结构简单，有效。链表中每个结点有三个信息段,LCHILD,DATA和 RCHILD
③ 堆,堆是一棵完全二元树，它的每个结点的值至少和该结点的儿子们（如果存在的话）的值一样大（ max-堆）（或小,min-堆）。
④ 二分检索树,二分检索树Ｔ是一棵二元树，
它或者为空，或者其每个结点含有一个可以比较大小的数据元素，且有：
· Ｔ的左子树的所有元素比根结点中的元素小；
· Ｔ的右子树的所有元素比根结点中的元素大；
· Ｔ的左子树和右子树也是二分检索树。
注：二分检索树要求树中所有结点的元素值互异
3,树的应用 ——不相交集合的合并及搜索问题
问题描述：
给定一个全集 U，该集合包含 n个元素
很明显该集合包含多个 不相交的子集
某些应用需要实现这些 不相交子集的合并,查找 操作，并且这些操作最终可形成 序列
如何高效率实现这些操作序列就是我们要解决的问题集合操作举例
n=10,U={1,2,3,4,5,6,7,8,9,10}
s1={1,7,8,9}; s2={2,5,10}; s3={3,4,6}
合并运算,s1∪ s2={1,7,8,9,2,5,10}
查找运算,元素 4包含在 s1,s2,s3的哪个集合中？
方法一 ——位向量
方法一：位向量
s1= {1,0,0,0,0,0,1,1,1,0}；
s2= {0,1,0,0,1,0,0,0,0,1}；
利用位运算可得出
s1∪ s2= {1,1,0,0,1,0,1,1,1,1}
缺点,n很大，超过一个机器字长，而参与运算的集合的势很小时，运算与 n成正比。
方法二 ——集合元素表
s1={1,7,8,9};
s2={2,5,10}
合并操作,| s1|+| s1|
查找操作：最坏为 |n|
方法三 ——树
1
7 8 9
S 1
2
5
1 0
S 2
2
5
1 0
S 2
1
7 8 9
S 1 ∪
2
5
1 0
1
7 8 9
数据结构
字符数组 U={1,2,3,4,5,6,7,8,9,10}
子集 s1={1,7,8,9}; s2={2,5,10}
则用数组 Parent表示集合 s1和 s2：数组中记录的是节点 U[i]的父节点在 Parent中的位置
（ 1） （ 2） （ 3） （ 4） （ 5） （ 6） （ 7） （ 8） （ 9） （ 10）
0 0 … … 2 … 1 1 1 2
合并操作 U(1,2)后：（ Parent[1]=2）
（ 1） （ 2） （ 3） （ 4） （ 5） （ 6） （ 7） （ 8） （ 9） （ 10）
2 0 … … 2 … 1 1 1 2
查找元素 F(9)
U操作为常量时间,F操作则与查找元素在集合树中的层数有关。
U和 F的性能问题 ——退化树
问题描述：有集合如下：
（ 1）（ 2） … （ n）
0 0 0
依次作下列操作：
U(1,2),F(1),U(2,3),
F(1),…,U(n -1,n)
按照算法 U和 F，最终得到的树及时间耗费分析
U：每次都是常量时间，
因此总共是 O(n-1)
F(1),2+3+…+(n -1)，
因此是 O(n^2)
症结？合并操作！
1
...
N-1
N
加权规则
节点数少的树合并到节点数多的树中。
字符数组 U={1,2,3,4,5,6,7,8,9,10}
子集 s1={1,7,8,9}; s2={2,5,10}
（ 1） （ 2） （ 3） （ 4） （ 5） （ 6） （ 7） （ 8） （ 9） （ 10）
-4 -3 … … 2 … 1 1 1 2
Union F序列演示分析
Union(1,2),F(1),Union (2,3),F(1),…,Union
(n-1,n)
Union合并的开销较 u要大，但仍然是常量时间
每次查找 1耗费时间为 2，常量时间，则执行 n-
2次查找耗费时间为 O(n)
注意：本例的查找耗时不是最坏情况
最坏情况由引理 1.3给出引理 1.3
引理 1.3 设 T是一棵由算法 union所产生的有 n个节点的树。在 T中没有节点的级数会大于（ logn的下界 +1）
证明,n=1，显然引理为真；
i为 T的级数，假设当 i<=n-1时，引理为真，现证对于
i=n，引理也为真；
令 k和 j是形成树 T的最后一次合并，即 Union(k,j)；
用 count()表示数的节点数，假设 count(j)=m，那么
count(k)=n-m；
不失一般性，可假设 1<=m<n/2，则有 m<=n-m；
那么经 Union合并后,j的父亲为 k；如右图：
则 T的级数：
1）等于 k的级数,log(n-m)的下界 +1<=（ logn的下界
+1）
2）或者等于（ j的级数 +1）：（ logm的下界 +2） <=
（ log(n/2)的下界 +2） <=（ logn的下界 +1）
得证
K
J
...
压缩规则
更快的平均查找时间，适用于频繁查找操作
例 1.2 在下图示例中实现 8次对元素 8的查找，
用 Find(8)算法实现
总共 20次，优于使用 F的 8*3=24次
结论：对于 m次 Find和 n次 Union的混合序列
（ m>=n），处理时间接近 O(m)，但稍差。详细描述见引理 1.4。
例 1.2
4,图图Ｇ 由称之为结点Ｖ和边Ｅ的两个集合组成，
记为 G=（ V,E）。其中，Ｖ是一个有限非空的结点集合；Ｅ是结点对偶的集合，Ｅ的每一对偶表示Ｇ的一条边。
有关图的的重要概念
无向图,边的表示（ｉ，ｊ）
有向图,边的表示 〈 ｉ，ｊ 〉
成本,带有成本的图称为网络
邻接,
结点的度（出度／入度 ）
路径,由结点 vp到 vq的一条路（ path）是结点
vp,vi1,vi2,?,vim,vq的一个序列，它使得 ( vp,vi1 ),( vi1,vi2 ),?,
( vim,vq )是 E（ G）的边。
路的长度,组成路的边数。
简单路径,除了第一和最后一个结点可以相同以外，
其它所有结点都不同。
环,第一个和最后一个结点相同的简单路。
连通图,在无向图中，如果每对结点之间都存在一条路，则称该图是连通的。
子图,是由 G的结点集 V的子集（记为 VB）和边集 E
中连接 VB中结点的边的子集所组成的图。
连通分图,一个图的最大连通子图。
有向图的强连通性,在有向图中，如果对于每一对结点 i和 j，既存在一条从 i到 j的路，又存在一条从 j
到 i的路，则称该有向图是强连通的。
图的表示方法
邻接矩阵 邻接表
1.5 递归和消去递归
1,递归
直接调用自己或间接通过一些语句调用自己
递归是一种强有力的设计方法
描述某些数学问题非常自然，易于证明算法
递归的效率问题
执行时间、空间消耗多例 1.3 斐波那契 (Fibonacci)序列：
F0 = F1 = 1
Fi = Fi-1 + Fi-2 （ i>1)
算法 1.7 求斐波那契数
procedure F(n)
//返回第 n个斐波那契数 //
integer n
if n<= 1 then return(1)
else return(F(n-1) + F(n-2))
endif
end F
算法效率：对 F(n-1),F(n-2)存在大量的重复计算
改 进：保存中间结果例 1.4 欧几里得算法已知两个非负整数 a和 b，且 a＞ b≥0,求这两个数的最大公因数。
辗转相除法,若 b=0，则 a和 b的最大公因数等于 a；
若 b＞ 0，则 a和 b的最大公因数等于 b和用 b除 a的余数的最大公因数。
算法 1.8 求最大公因数
procedure GCD(a,b) // 约定 a>b //
if b=0 then return(a)
else return (GCD(b,a mod b))
endif
end GCD
例,GCD(22,8) = GCD(8,6) = GCD(6,2) = GCD(2,0) = 2;
GCD(22,8)
GCD(8,6)
GCD(6,2)
GCD(2,0)
2
递推递 推递 推递 推回 归回 归回 归回归 结果为
GCD(22,8)=2
例 1.5 递归在 非数值算法 设计中的应用已知元素 x，判断 x是否在 A（ 1,n）中。
算法 1.9 在 A（ 1,n）中检索 x
procedure SEARCH(i)
//如果在 A（ 1,n）中有一元素 A（ k） =x，则将其第一次出现的下标 k返回，否则返回 0//
global n,x,A(1:n)
case
:i>n,return(0)
:A(i) = x; return(i)
:else,return(SEARCH(i+1))
endcase
end SEARCH
2,消去递归直接递归的消去规则,
基本思路,将递归过程中出现递归调用的地方，用等价的 非递归代码 来代替，并对 return语句 做适当处理。
13条规则,处理直接递归调用中的递归代码和 return
语句，将之转换成等价的迭代代码。
初始化
⑴ 在过程的开始部分，插入说明为栈的代码并将其初始化为空。在一般情况下，这个栈用来存放参数、局部变量和函数的值、每次递归调用的返回地址。
⑵ 将标号 L1附于第一条可执行语句。然后对于每一处递归调用都用一组执行下列规则的指令来代替。
处理递归调用语句
⑶ 将所有参数和局部变量的值存入栈。
栈顶指针 可作为一个全程变量来看待。
⑷ 建立第 i个新标号 Li，并将 i存入栈。这个标号的 i
值将用来计算返回地址。
此标号放在规则⑺所描述的程序段中。
⑸ 计算这次调用的各实在参数（可能是表达式）的值，并把这些值赋给相应的形式参数。
⑹ 插入一条无条件转向语句转向过程的开始部分：
Goto L1
对递归嵌套调用的处理
⑺ 如果这过程是函数，则对递归过程中含有此次函数调用的那条语句做如下处理：将该语句的此次函数调用部分用从栈顶取回该函数值的代码来代替，其余部分的代码按原描述方式照抄，并将⑷中建立的标号附于这条语句上。
如果此过程不是函数，则将⑷中建立的标号附于⑹
所产生的转移语句后面的那条语句。
以上步骤实现消去过程中的递归调用。下面对过程中出现 return语句 进行处理（纯过程结束处的 end可看成是一条没有值与之联系的 return语句）。
对每个有 return语句的地方，执行下述规则,
⑻ 如果栈为 空,则执行 正常返回 。
⑼ 否则，将所有输出参数（带有返回值的出口参数，
out/inout型）的当前值赋给栈顶上的那些对应的变量。
⑽ 如果栈中有返回地址标号的下标，就插入一条此下标从栈中退出的代码，并把这个下标赋给一个未使用的变量。
⑾ 从栈中退出所有局部变量和参数的值并吧它们赋给对应的变量。
⑿ 如果这个过程是函数，则插入以下指令，这些指令用来计算紧接在 return后面的表达式并将结果值存入栈顶。
⒀ 用返回地址标号的下标实现对该标号的转向。
例 1.6 递归调用示例求数组元素中的最大值算法 1.10 递归求取数组元素的最大值
procedure MAX1(i)
// 查找数组 A中最大值元素，并返回该元素的最大下标。 //
global integer n,A(1:n),j,k
integer i
if i<n then j←MAX1(i+1) //递归调用 //
if A(i) > A(j) then k←i
else k←j
endif
else k←n
endif
return(k) //递归调用的返回 //
end MAX1
消去上例中的递归
算法 1.11 使用上述的规则消去例 1.10中的递归代码
procedure MAX2(i)
local integer j,k; global integer n,A(1:n)
integer I
integer STACK(1:2*n)
top←0 //规则 1，声明栈的代码，并初始化为空 //
L1,if i<n //规则 2，将标号 L1赋于第一条可执行语句前 //
then top ←top + 1; STACK(top)← i; // 规则 3，参数或局部变量的值入栈 //
top ←top +1; STACK(top)← 2; // 规则 4，建立新的标号 2，并入栈 //
i ← i+1 // 规则 5,计算参数值 //
goto L1 //规则 6,无条件转向算法的开始部分 //
L2,j ←STACK(top); top ←top -1; // 规则 7,处理函数调用，
并将标号 2赋于该语句上 //
if A(i) > A(j) then k ←I
else k ←j
endif
else k ←n
endif
if top = 0 then return(k) // 规则 8,如果栈空，则正常返回 //
else addr ←STACK(top);top ←top -1; // 规则 10,从栈中退出返回标号 //
i ←STACK(top);top ←top -1; // 规则 11,从栈中退出局部变量和参数的值 //
top ←top+1;STACK(top) ← k; // 规则 12,计算返回值，并将之入栈 //
if addr = 2 then goto L2 endif // 规则 13,用返回地址标号的下标实现对该标号的转向 //
endif
end MAX2
进一步优化和简化经过消去递归产生的迭代程序。
算法 1.12 算法 1.11的改进模型
procedure MAX3(A,n)
integer i,k,n;
i ←k ←n
while i>1 do
i ←i -1
if A(i) >A(k) then k ←i endif
repeat
return(k)
end MAX3
不必死套 13条规则，应具体情况具体分析
procedure GCD1(a,b) // 约定 a>b //
L1,if b=0 then return(a)
else t ←b;b ←a mod b;a ←t;go to L1
endif
end GCD1
整理后得,
procedure GCD2(a,b)
while b≠ 0 do
t ←b;b ←a mod b;a ←t
repeat
return(a)
end GCD2
递归式分析
代换法
猜测
验证
找到常量的范围
递归树
主定理
三种情况
需要记忆代换法 ——例子一
T(n)=2T(n/2)+n
假设,T(1) = Θ(1)
猜测上界函数为,O(nlgn)
证明：
有 T(k) ≤ cnlgn,k < n
则 T(n) ≤ 2c(n/2)lg(n/2)+n ＝ cnlg(n/2)+n
＝ cnlgn-cnlg2+n ＝ cnlgn-(cn-n) ≤cnlgn
常数,c大于等于 1
代换法 ——避免陷阱
T(n)=2T(n/2)+n
假设,T(1) = Θ(1)
猜测上界函数为,O(n)
证明：
有 T(k) ≤ cn,k < n
则 T(n) ≤ 2c(n/2)+n ＝ cn+n ＝ O(n) 错！
常数,c大于等于 1
代换法 ——例子二（小技巧）
T(n)=2T(n/2)+1
假设,T(1) = Θ(1)
猜测上界函数为,O(n)
证明：
有 T(k) ≤ cn,k < n
则 T(n) ≤ 2c(n/2)+1 ＝ cn+1 怎么办？ O(nlgn)?
加强条件 T(k) ≤ cn-b,其中 b>=0
T(n) ≤ 2(c(n/2)-b)+1=cn-(2b-1) ≤ cn
常数,b大于等于 1/2,c取足够大递归树方法
T(n)=3T(n/4)+cn2
T(n)=T(n/3)+T(2n/3)+O(n)
主方法
递归式形式如下,T(n) = aT(n/b) + f(n),其中
a ≥ 1,b > 1,f(n)是渐近的正函数
主定理：比较 f (n) 和 nlogba:
f (n) = O(nlogba –ε),常数 ε > 0,T(n) = Θ(nlogba)
f (n) = Θ(nlogba lgkn),常数 k ≥ 0,T(n) = Θ(nlogba
lgk+1n)
f (n) = O(nlogba +ε),常数 ε > 0,T(n) = Θ( f (n))
主方法 ——例子
T(n)=9T(n/3)+n
T(n)=T(2n/3)+1
T(n)=2T(n/2)+nlgn
问题是否可解
1930’s 研究集中于判断特定问题在计算机上是否可解，基本方法为：选定一个计算模型，观察是否能在该模型上创建能解决问题的算法。这些计算模型包括,Post machines,Turing machines等。这一阶段的成果是,大部分问题为不可解 。
高效率的解决方法
随着计算机的发展和数据资源的增加，算法研究转向针对可解的问题，找到高效率的解决方法。
算法的应用
数据库中的检索
搜索引擎中的爬找器和检索
公共密钥加密和数字签名技术
优化问题
最短路径
资源分配
…
章节安排
,计算机算法基础,,余祥宣、崔国华、邹海明著，华中科技大学出版社
第一章 导引与基本数据结构 √
第二章 分治法 √
第三章 贪心方法 √
第四章 动态规划 √
第五章 检索与周游 √
第六章 回溯法 √
第七章 分枝 -限界 √
第八章 NP-问题 ⊙
预备知识
数学：集合、证明方法（直接、间接、反证、
反例、归纳假设）、对数基础、
FLOOR&CEILING函数、阶乘、递归关系
数据结构：链接表、图、树、二元树第一章 导引与基本数据结构
1.1 算法的定义及特性
1,什么是算法？
算法是解一 确定类问题 的任意一种 特殊的方法 。
在计算机科学中，算法是使用计算机解 一类问题 的精确、有效方法的代名词：
算法 是一组 有穷的规则,它规定了解决某一 特定类型问题 的一系列 运算 。
2,算法的五个重要特性确定性,能行性,输入,输出,有穷性
1） 确定性,算法的每种运算必须要有确切的定义，不能有二义性。
例：不符合确定性的运算
5/0
将 6或 7与 x相加
未赋值变量参与运算
2） 能行性算法中有待实现的运算都是基本的运算，
原理上每种运算都能由人用纸和笔在有限的时间内完成。
例：整数的算术运算是“能行”的实数的算术运算是,不能行” 的
3） 输入每个算法有 0个或 多 个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合 ——定义域 （或值域）
4） 输出一个算法产生 一个 或 多个 输出，这些输出是同输入有某种特定关系的量。
5） 有穷性一个算法总是在执行了 有穷步 的运算之后 终止 。
计算过程,只满足确定性、能行性、输入、输出四个特性但 不一定能终止 的一组规则。
准确理解算法和计算过程的区别：
不能终止的计算过程：操作系统
算法是“可以终止的计算过程”
算法的时效性：只能把在 相当 有穷步内终止的算法投入到计算机上运行
3,我们的主要任务算法学习将涉及 5个方面的内容：
1） 设计算法,创造性的活动
2） 表示算法,思想的表示形式
3） 确认算法,证明算法的正确性程序的证明
4） 分析算法,算法时空特性分析
5） 测试程序,调试和作出时空分布图本课程集中于学习算法的 设计 与 分析 。通过学习，掌握计算机算法设计和分析 基本策略与方法,
为设计更复杂、更有效的算法奠定基础
1.2 分析算法
1,分析算法的目的在于：通过对算法的分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物力浪费。
算法分析是计算机领域的古老而前沿的课题。
进行算法分析的基本技术：抽象
2,重要的假设和约定
1）计算机模型的假设
Turing机模型：计算机形式理论模型
通用计算机模型：
单处理器
有足够的“内存”
能在固定的时间内存取数据单元
2）计算的约定
确定使用什么样的运算及其执行时间。
从计算时间上，运算的分类：
时间囿界于常数的运算,尽管每种运算的执行时间不同，但一般只花 一个 固定量 的时间（单位时间）
就可完成。
· 基本算术运算，如整数、浮点数的加、减、乘、除
· 字符运算
· 赋值 运算
· 过程调用等
2）计算的约定（续）
其他运算,
· 字符串操作：与字符串中字符的数量成正比
· 记录操作：与记录的属性数、属性类型等有关
· 特点：运算时间 无定量如何分析非时间囿界于常数的运算：分解成若干时间囿界于常数的运算。
如,Tstring = Length（ String） * tchar
算法的执行时间 =∑Fi*ti
其中,Fi是算法中用到的某种运算 i的次数,ti是该运算执行一次所用的时间。
3）工作数据集的选择
编制能够反映算法在最好、平均、最坏情况下工作的 数据配置 。然后使用这些数据配置运行算法，
以了解算法的性能。
测试数据集的生成
作为算法分析的数据集：典型特征
作为程序性能测试的数据集：对执行指标产生影响的性质
3,如何进行算法分析？
对算法进行全面分析，可分两个阶段进行：
事前分析,就算法本身，通过对其执行性能的理论分析，
得出关于算法特性 ——时间和空间 的一个特征函数（ Ο,Ω） ——与计算机物理软硬件没有直接关系。
事后测试,将算法编制成程序后实际放到计算机上运行，
收集其执行时间和空间占用等统计资料，进行分析判断 ——直接与物理实现有关。
1）事前分析
目的：试图得出关于算法执行特性的一种形式描述，以“理论上”衡量算法的“好坏”。
如何给出反映算法执行特性的描述？
最直接方法,统计算法中各种运算的执行情况，包括：
运用了哪些运算
每种运算被执行的次数
该种运算执行一次所花费的时间等。
算法的执行时间 =∑Fi*ti
频率计数例：
x←x+y for i ←1 to n do for i ←1 to n do
x ← x + y for j ←1 to n do
repeat x ← x +y
repeat
repeat
(a) (b) (c)
分析：
(a),x←x+y 执行了 1次
(b),x←x+y 执行了 n次
(c),x←x+y 执行了 n2次定义：
频率计数,一条 语句 或一种 运算 在算法（或程序）体中的执行次数。
算法 2.7 插入分类
procedure INSERTIONSORT(A,n)
//将 A(1,n)中的元素按非降次序分类,n≥1//
1 A(0)← -∞//设置初始边界值
2 for j←2 to n do //A(1:j -1)已分类 //
3 item←A(j);i←j -1
4 while item<A(i) do //0≤i<j//
5 A(i+1)←A(i); i←i -1
6 repeat
7 A(i+1) ←item;
8 repeat
end INSERTIONSORT
(8,5,4,9)
(8,5,4,9)
(5,8,4,9)
(5,8,4,9)
(4,5,8,9)
(4,5,8,9)
一条语句在整个程序运行时实际执行时间 =
频率计数 * 每执行一次该语句所需的时间
如何刻画算法执行特性的形式描述
实际执行时间受约于诸多实际因素，如机器类型、编程与语言、操作系统等，没有统一的描述模型。
在事前分析中，只限于确定与所使用的机器及其他环境因素无关的频率计数，依此建立理论分析模型。
数量级
语句的数量级,语句的执行频率例,1,n,n2
算法的数量级,算法所包含的所有语句的执行频率之和。
算法的数量级从本质上反映了一个算法的执行特性。
例：假如求解同一个问题的三个算法分别具有 n,n2,n3数量级。
若 n=10，则可能的执行时间将分别是 10,100,1000个单位时间 ——与环境因素无关。
计算时间 /频率计数的表示函数通过事前分析给出算法计算时间（频率计数）的一个 函数 表示形式，一般记为与 输入规模
n有关的函数形式,f(n)
注：最高次项与函数整体的关系
空间特性分析（略）
2）事后测试
目的：运行程序，确定程序实际耗费的时间与空间，验证先前的分析结论 ——包括正确性、执行性能等，比较、优化所设计的算法。
分析手段：作时、空性能分布图
4,计算时间的渐近表示记：算法的计算时间为 f(n)
数量级限界函数为 g(n)
其中，
n是输入或输出规模的某种测度。
f(n)表示算法的“实际”执行时间 —与机器及语言有关 。
g(n)是 形式简单 的函数，如 nm,logn,2n,n!等。是事前分析中通过对计算时间或频率计数统计分析所得的,与机器及语言无关 的函数。
以下给出算法执行时间,上界 （ О）,下界 （ Ω ）、
“平均” （ ）的定义。
1）上界函数定义 1 如果存在两个正常数 c和 n0，对于所有的 n≥n 0，有
|f(n)| ≤ c|g(n)|
则记作 f(n) = Ο(g(n))
含义：
如果算法用 n值不变的同一类数据在某台机器上运行时，所用的时间总是小于 |g(n)|的一个常数倍。所以 g(n)是计算时间 f(n)的一个 上界函数 。 f(n)的数量级就是 g(n)。
试图求出 最小 的 g(n)，使得 f(n) = Ο(g(n))。
多项式定理,
定理 1 若 A(n) = amnm+?+a 1n+a0是一个 m次多项式，则有 A(n) = Ο(nm)
即：变量 n的固定阶数为 m的任一多项式，与此多项式的最高阶 nm同阶。
证明：取 n0=1,当 n≥n 0时，有
|A(n)|≤|am|nm+…+|a 1|n+|a0|
≤(|am|+|am-1|/n+…+|a 0|/nm) nm
≤(|am|+|am-1|+…+|a 0|) nm
令 c= |am|+|am-1|+…+|a 0|
则，定理得证。
计算时间的数量级对算法有效性的影响数量级 的大小对算法的有效性有 决定性 的影响。
例：假设解决同一个问题的两个算法，它们都有 n个输入，计算时间的数量级分别是 n2和 nlogn。则，
n=1024：分别需要 1048576和 10240次运算。
n=2048：分别需要 4194304和 22528次运算。
分析：在 n加倍的情况下，一个 Ο(n2)的算法计算时间增长 4
倍，而一个 Ο(nlogn)算法则只用 两 倍多一点的时间即可完成。
算法 2.8 归并分类
procedure MERGESORT(low,high)
//A(low:high)是一个全程数组，它含有 high-low+1≥0 个待分类的元素 //
integer low,high
if low<high then
mid← //计算 中分点 //
call MERGESORT(low,mid) //在第一个子集合上分类 (递归 )//
call MERGESORT(mid+1,high) //在第二个子集合上分类 (递归 )//
call MERGE(low,mid,high) //归并已分类的两子集合 //
endif
end MERGESORT
h ig h )/ 2(lo w?
Merge算法示例
(4,5,8,9)|(1,2,6,7)? (1,2,4,5,6,7,8,9)
参数,low = 1; high = 8; mid = 4
(4,5,8,9)|( 1,2,6,7)
h j j j jh h
(1 42 5 6 7 8 9)
j
算法分类（计算时间）
多项式时间算法：可用多项式（函数）对其计算时间限界的算法。
常见的多项式限界函数有：
Ο(1) < Ο(logn) < Ο(n) < Ο(nlogn) < Ο(n2) < Ο(n3)
指数时间算法：计算时间用指数函数限界的算法常见的指数时间限界函数：
Ο(2n) < Ο(n！ ) < Ο(nn)
说明：当 n取值较大时，指数时间算法和多项式时间算法在计算时间上非常悬殊。
典型的计算时间函数曲线
当数据集的规模很大时，要在现有的计算机系统上运行具有比 Ο(nlogn)复杂度还高的算法是比较困难的。
指数时间算法只有在 n取值 非常小时 才实用。
要想在顺序处理机上扩大所处理问题的规模，有效的途径是 降低算法的计算复杂度,而不是（仅仅依靠）提高计算机的速度。
计算时间函数值比较定义 1.2 如果存在两个正常数 c和 n0，对于所有的 n≥n 0，
有
|f(n)| ≥ c|g(n)|
则记作 f(n) = Ω(g(n))
含义：
如果算法用 n值不变的同一类数据在某台机器上运行时，所用的时间总是不小于 |g(n)|的一个常数倍。所以 g(n)是计算时间 f(n)的一个下 界函数 。
试图求出,最大,的 g(n)，使得 f(n) = Ω(g(n))。
2）下界函数定义 1.3 如果存在正常数 c1,c2和 n0，对于所有的 n≥n 0，
有
c1|g(n)| ≤|f(n)| ≤ c 2|g(n)|
则记作含义：
算法在最好和最坏情况下的计算时间就一个常数因子范围内而言是相同的。可看作：
既有 f(n) = Ω(g(n))，又有 f(n) = Ο(g(n))
))(()( ngnf
3）“平均情况”限界函数
4）限界函数的性质
1）若 且,则 。即 О具有传递性。（ 同）
2） 当且仅当
3）若,则 。即,定义了一个等价关系（等价类）
)(gf )(hg )(hf
、
)(gf )( fg
)(gf )( fg
5,常用的整数求和公式在算法分析中，在统计语句的频率时，求和公式的一般表示形式为：
如：
h ( n )i)(
)(
ng
if
)( 1
1
k
ni
k ni
1+1+…+1 （有 n项 1） = n
1+2+…+n = n 2
12+ 22 +…+ n 2 = n3
20+ 21 +…+ 2 n = 2n+1?
1.3 关于 SPARKS语言
本书为描述算法选用的一种类计算机语言
类 PASCAL语言
结构化程序描述
1,基本语法成分
1）数据类型：整型、实型、布尔型、字符型
2）变量声明,integer i,j; boolean b; char c
3）赋值运算,（变量） ← （表达式）
4）逻辑运算,and or not
5）关系运算：＜ ≤ ＝ ≠ ≥ ＞
6）变量声明：类型说明符 变量；
7）数组声明,integer A（ 1,5,7,20）
8）控制结构：
顺序,
分支,
· if condition then S1
else S2
endif
· case
:cond1:S1;
:cond2:S2;
…
:condn:Sn
:else:Sn+1
endcase
循环,
· while cond do
S
repeat
· loop
S
until cond repeat
· for vble←start to finish by increment do
S
repeat
2,同质异项
3,其它函数的定义与调用、函数和过程、变量与形式参数
1.4 基本数据结构
1,栈和队列
栈和队列,n个元素的线性表
利用动态数据结构 ——链表 实现栈或队列
利用静态数据结构 ——数组 实现栈或队列
基于以上两种表示形式的栈和队列上的基本运算队列的数组表示栈的数组表示用一维数组 STACKS（ 1:n）表示栈底,STACKS（ 1） 第 i个元素 STACKS(i)
栈顶指针,top
procedure ADD(item,STACAK,n,top)
if top ≥ n then call STACKFULL
endif
top← top +1
STACK(top) ← item
end add
procedure DELETE(item,STACK,top)
if top ≤ 0 then call STACKEMPTY
endif
item ← STACK(top)
top ← top-1
end DELETE
栈的数组表示 ——增加、删除栈的链接表表示一种单向链接表两个信息段,DATA存放数据,LINK指向前一节点节点插入
call GETNODE(T)
DATA(T) ←item
LINK(T) ←STACK
STACK ← T
节点删除
item ←DATA(STACK)
T ←STACK
STACK ←LINK(SATCK)
call RETNODE(T)
A
STACK
0
栈的链接表表示 ——增加、删除
2,树
1）树的一般定义定义 1.4 树（ tree） 是一个或多个结点的 有限 集合，它使得：
有一个指定为 根 （ root）的结点
剩余结点被划分成 m≥0 个不相交的集合：
T1,?,Tm
这些集合的每一个又都是一棵树，并称 T1,?,Tm为根的子树。
关于树的重要概念
结点的度 （ degree）：一个结点的子树数
树的度,树中结点度的最大值
结点的级 （ level）（又叫层）：设根是 1级，若某结点在 p级，则它的儿子在 p+1级
树的高度（或深度）,树中结点的最大级数
叶子（终端结点）,度为 0的结点
内结点（非终端结点）,度不为 0的结点
森林,m≥0 个不相交树的集合。
树的表示方法用 链接表 表示每个结点三个信息段：
TAG,DATA,LI
NK
TAG＝ 0，
DATA存数据；
TAG=1,DATA
存链接信息，
指向一棵子树
2）二元树定义 1.5 二元树 （ binary tree）是结点的有限集合，它或者为 空,或者由一个根和两棵称为左子树和右子树的不相交二元树所组成。
二元树与度为 2的树的区别
二元树性质 1：
引理 1.1 一棵二元树第 i级的最大结点数是 2i-1。深度为 k的二元树的最大结点数为 2k-1,k>0。
特殊形态的二元树
满二元树,深度为 k且有 2k-1个结点的二元树
完全二元树,一棵有 n个结点深度为 k的二元树，
当它的结点相当于深度为 k的满二元树中编号为 1到 n的结点时，称该二元树是完全的。
完全二元树的叶子结点至多出现在相邻的两级上。
完全二元树的结点可以紧凑地存放在一个一维数组中（性质见引理 1.2）。
二元树的表示方法
1.数组表示法：对于完全二元树，空间效率好；其他二元树，要浪费大量空间
2.链表法：结构简单，有效。链表中每个结点有三个信息段,LCHILD,DATA和 RCHILD
③ 堆,堆是一棵完全二元树，它的每个结点的值至少和该结点的儿子们（如果存在的话）的值一样大（ max-堆）（或小,min-堆）。
④ 二分检索树,二分检索树Ｔ是一棵二元树，
它或者为空，或者其每个结点含有一个可以比较大小的数据元素，且有：
· Ｔ的左子树的所有元素比根结点中的元素小；
· Ｔ的右子树的所有元素比根结点中的元素大；
· Ｔ的左子树和右子树也是二分检索树。
注：二分检索树要求树中所有结点的元素值互异
3,树的应用 ——不相交集合的合并及搜索问题
问题描述：
给定一个全集 U，该集合包含 n个元素
很明显该集合包含多个 不相交的子集
某些应用需要实现这些 不相交子集的合并,查找 操作，并且这些操作最终可形成 序列
如何高效率实现这些操作序列就是我们要解决的问题集合操作举例
n=10,U={1,2,3,4,5,6,7,8,9,10}
s1={1,7,8,9}; s2={2,5,10}; s3={3,4,6}
合并运算,s1∪ s2={1,7,8,9,2,5,10}
查找运算,元素 4包含在 s1,s2,s3的哪个集合中？
方法一 ——位向量
方法一：位向量
s1= {1,0,0,0,0,0,1,1,1,0}；
s2= {0,1,0,0,1,0,0,0,0,1}；
利用位运算可得出
s1∪ s2= {1,1,0,0,1,0,1,1,1,1}
缺点,n很大，超过一个机器字长，而参与运算的集合的势很小时，运算与 n成正比。
方法二 ——集合元素表
s1={1,7,8,9};
s2={2,5,10}
合并操作,| s1|+| s1|
查找操作：最坏为 |n|
方法三 ——树
1
7 8 9
S 1
2
5
1 0
S 2
2
5
1 0
S 2
1
7 8 9
S 1 ∪
2
5
1 0
1
7 8 9
数据结构
字符数组 U={1,2,3,4,5,6,7,8,9,10}
子集 s1={1,7,8,9}; s2={2,5,10}
则用数组 Parent表示集合 s1和 s2：数组中记录的是节点 U[i]的父节点在 Parent中的位置
（ 1） （ 2） （ 3） （ 4） （ 5） （ 6） （ 7） （ 8） （ 9） （ 10）
0 0 … … 2 … 1 1 1 2
合并操作 U(1,2)后：（ Parent[1]=2）
（ 1） （ 2） （ 3） （ 4） （ 5） （ 6） （ 7） （ 8） （ 9） （ 10）
2 0 … … 2 … 1 1 1 2
查找元素 F(9)
U操作为常量时间,F操作则与查找元素在集合树中的层数有关。
U和 F的性能问题 ——退化树
问题描述：有集合如下：
（ 1）（ 2） … （ n）
0 0 0
依次作下列操作：
U(1,2),F(1),U(2,3),
F(1),…,U(n -1,n)
按照算法 U和 F，最终得到的树及时间耗费分析
U：每次都是常量时间，
因此总共是 O(n-1)
F(1),2+3+…+(n -1)，
因此是 O(n^2)
症结？合并操作！
1
...
N-1
N
加权规则
节点数少的树合并到节点数多的树中。
字符数组 U={1,2,3,4,5,6,7,8,9,10}
子集 s1={1,7,8,9}; s2={2,5,10}
（ 1） （ 2） （ 3） （ 4） （ 5） （ 6） （ 7） （ 8） （ 9） （ 10）
-4 -3 … … 2 … 1 1 1 2
Union F序列演示分析
Union(1,2),F(1),Union (2,3),F(1),…,Union
(n-1,n)
Union合并的开销较 u要大，但仍然是常量时间
每次查找 1耗费时间为 2，常量时间，则执行 n-
2次查找耗费时间为 O(n)
注意：本例的查找耗时不是最坏情况
最坏情况由引理 1.3给出引理 1.3
引理 1.3 设 T是一棵由算法 union所产生的有 n个节点的树。在 T中没有节点的级数会大于（ logn的下界 +1）
证明,n=1，显然引理为真；
i为 T的级数，假设当 i<=n-1时，引理为真，现证对于
i=n，引理也为真；
令 k和 j是形成树 T的最后一次合并，即 Union(k,j)；
用 count()表示数的节点数，假设 count(j)=m，那么
count(k)=n-m；
不失一般性，可假设 1<=m<n/2，则有 m<=n-m；
那么经 Union合并后,j的父亲为 k；如右图：
则 T的级数：
1）等于 k的级数,log(n-m)的下界 +1<=（ logn的下界
+1）
2）或者等于（ j的级数 +1）：（ logm的下界 +2） <=
（ log(n/2)的下界 +2） <=（ logn的下界 +1）
得证
K
J
...
压缩规则
更快的平均查找时间，适用于频繁查找操作
例 1.2 在下图示例中实现 8次对元素 8的查找，
用 Find(8)算法实现
总共 20次，优于使用 F的 8*3=24次
结论：对于 m次 Find和 n次 Union的混合序列
（ m>=n），处理时间接近 O(m)，但稍差。详细描述见引理 1.4。
例 1.2
4,图图Ｇ 由称之为结点Ｖ和边Ｅ的两个集合组成，
记为 G=（ V,E）。其中，Ｖ是一个有限非空的结点集合；Ｅ是结点对偶的集合，Ｅ的每一对偶表示Ｇ的一条边。
有关图的的重要概念
无向图,边的表示（ｉ，ｊ）
有向图,边的表示 〈 ｉ，ｊ 〉
成本,带有成本的图称为网络
邻接,
结点的度（出度／入度 ）
路径,由结点 vp到 vq的一条路（ path）是结点
vp,vi1,vi2,?,vim,vq的一个序列，它使得 ( vp,vi1 ),( vi1,vi2 ),?,
( vim,vq )是 E（ G）的边。
路的长度,组成路的边数。
简单路径,除了第一和最后一个结点可以相同以外，
其它所有结点都不同。
环,第一个和最后一个结点相同的简单路。
连通图,在无向图中，如果每对结点之间都存在一条路，则称该图是连通的。
子图,是由 G的结点集 V的子集（记为 VB）和边集 E
中连接 VB中结点的边的子集所组成的图。
连通分图,一个图的最大连通子图。
有向图的强连通性,在有向图中，如果对于每一对结点 i和 j，既存在一条从 i到 j的路，又存在一条从 j
到 i的路，则称该有向图是强连通的。
图的表示方法
邻接矩阵 邻接表
1.5 递归和消去递归
1,递归
直接调用自己或间接通过一些语句调用自己
递归是一种强有力的设计方法
描述某些数学问题非常自然，易于证明算法
递归的效率问题
执行时间、空间消耗多例 1.3 斐波那契 (Fibonacci)序列：
F0 = F1 = 1
Fi = Fi-1 + Fi-2 （ i>1)
算法 1.7 求斐波那契数
procedure F(n)
//返回第 n个斐波那契数 //
integer n
if n<= 1 then return(1)
else return(F(n-1) + F(n-2))
endif
end F
算法效率：对 F(n-1),F(n-2)存在大量的重复计算
改 进：保存中间结果例 1.4 欧几里得算法已知两个非负整数 a和 b，且 a＞ b≥0,求这两个数的最大公因数。
辗转相除法,若 b=0，则 a和 b的最大公因数等于 a；
若 b＞ 0，则 a和 b的最大公因数等于 b和用 b除 a的余数的最大公因数。
算法 1.8 求最大公因数
procedure GCD(a,b) // 约定 a>b //
if b=0 then return(a)
else return (GCD(b,a mod b))
endif
end GCD
例,GCD(22,8) = GCD(8,6) = GCD(6,2) = GCD(2,0) = 2;
GCD(22,8)
GCD(8,6)
GCD(6,2)
GCD(2,0)
2
递推递 推递 推递 推回 归回 归回 归回归 结果为
GCD(22,8)=2
例 1.5 递归在 非数值算法 设计中的应用已知元素 x，判断 x是否在 A（ 1,n）中。
算法 1.9 在 A（ 1,n）中检索 x
procedure SEARCH(i)
//如果在 A（ 1,n）中有一元素 A（ k） =x，则将其第一次出现的下标 k返回，否则返回 0//
global n,x,A(1:n)
case
:i>n,return(0)
:A(i) = x; return(i)
:else,return(SEARCH(i+1))
endcase
end SEARCH
2,消去递归直接递归的消去规则,
基本思路,将递归过程中出现递归调用的地方，用等价的 非递归代码 来代替，并对 return语句 做适当处理。
13条规则,处理直接递归调用中的递归代码和 return
语句，将之转换成等价的迭代代码。
初始化
⑴ 在过程的开始部分，插入说明为栈的代码并将其初始化为空。在一般情况下，这个栈用来存放参数、局部变量和函数的值、每次递归调用的返回地址。
⑵ 将标号 L1附于第一条可执行语句。然后对于每一处递归调用都用一组执行下列规则的指令来代替。
处理递归调用语句
⑶ 将所有参数和局部变量的值存入栈。
栈顶指针 可作为一个全程变量来看待。
⑷ 建立第 i个新标号 Li，并将 i存入栈。这个标号的 i
值将用来计算返回地址。
此标号放在规则⑺所描述的程序段中。
⑸ 计算这次调用的各实在参数（可能是表达式）的值，并把这些值赋给相应的形式参数。
⑹ 插入一条无条件转向语句转向过程的开始部分：
Goto L1
对递归嵌套调用的处理
⑺ 如果这过程是函数，则对递归过程中含有此次函数调用的那条语句做如下处理：将该语句的此次函数调用部分用从栈顶取回该函数值的代码来代替，其余部分的代码按原描述方式照抄，并将⑷中建立的标号附于这条语句上。
如果此过程不是函数，则将⑷中建立的标号附于⑹
所产生的转移语句后面的那条语句。
以上步骤实现消去过程中的递归调用。下面对过程中出现 return语句 进行处理（纯过程结束处的 end可看成是一条没有值与之联系的 return语句）。
对每个有 return语句的地方，执行下述规则,
⑻ 如果栈为 空,则执行 正常返回 。
⑼ 否则，将所有输出参数（带有返回值的出口参数，
out/inout型）的当前值赋给栈顶上的那些对应的变量。
⑽ 如果栈中有返回地址标号的下标，就插入一条此下标从栈中退出的代码，并把这个下标赋给一个未使用的变量。
⑾ 从栈中退出所有局部变量和参数的值并吧它们赋给对应的变量。
⑿ 如果这个过程是函数，则插入以下指令，这些指令用来计算紧接在 return后面的表达式并将结果值存入栈顶。
⒀ 用返回地址标号的下标实现对该标号的转向。
例 1.6 递归调用示例求数组元素中的最大值算法 1.10 递归求取数组元素的最大值
procedure MAX1(i)
// 查找数组 A中最大值元素，并返回该元素的最大下标。 //
global integer n,A(1:n),j,k
integer i
if i<n then j←MAX1(i+1) //递归调用 //
if A(i) > A(j) then k←i
else k←j
endif
else k←n
endif
return(k) //递归调用的返回 //
end MAX1
消去上例中的递归
算法 1.11 使用上述的规则消去例 1.10中的递归代码
procedure MAX2(i)
local integer j,k; global integer n,A(1:n)
integer I
integer STACK(1:2*n)
top←0 //规则 1，声明栈的代码，并初始化为空 //
L1,if i<n //规则 2，将标号 L1赋于第一条可执行语句前 //
then top ←top + 1; STACK(top)← i; // 规则 3，参数或局部变量的值入栈 //
top ←top +1; STACK(top)← 2; // 规则 4，建立新的标号 2，并入栈 //
i ← i+1 // 规则 5,计算参数值 //
goto L1 //规则 6,无条件转向算法的开始部分 //
L2,j ←STACK(top); top ←top -1; // 规则 7,处理函数调用，
并将标号 2赋于该语句上 //
if A(i) > A(j) then k ←I
else k ←j
endif
else k ←n
endif
if top = 0 then return(k) // 规则 8,如果栈空，则正常返回 //
else addr ←STACK(top);top ←top -1; // 规则 10,从栈中退出返回标号 //
i ←STACK(top);top ←top -1; // 规则 11,从栈中退出局部变量和参数的值 //
top ←top+1;STACK(top) ← k; // 规则 12,计算返回值，并将之入栈 //
if addr = 2 then goto L2 endif // 规则 13,用返回地址标号的下标实现对该标号的转向 //
endif
end MAX2
进一步优化和简化经过消去递归产生的迭代程序。
算法 1.12 算法 1.11的改进模型
procedure MAX3(A,n)
integer i,k,n;
i ←k ←n
while i>1 do
i ←i -1
if A(i) >A(k) then k ←i endif
repeat
return(k)
end MAX3
不必死套 13条规则，应具体情况具体分析
procedure GCD1(a,b) // 约定 a>b //
L1,if b=0 then return(a)
else t ←b;b ←a mod b;a ←t;go to L1
endif
end GCD1
整理后得,
procedure GCD2(a,b)
while b≠ 0 do
t ←b;b ←a mod b;a ←t
repeat
return(a)
end GCD2
递归式分析
代换法
猜测
验证
找到常量的范围
递归树
主定理
三种情况
需要记忆代换法 ——例子一
T(n)=2T(n/2)+n
假设,T(1) = Θ(1)
猜测上界函数为,O(nlgn)
证明：
有 T(k) ≤ cnlgn,k < n
则 T(n) ≤ 2c(n/2)lg(n/2)+n ＝ cnlg(n/2)+n
＝ cnlgn-cnlg2+n ＝ cnlgn-(cn-n) ≤cnlgn
常数,c大于等于 1
代换法 ——避免陷阱
T(n)=2T(n/2)+n
假设,T(1) = Θ(1)
猜测上界函数为,O(n)
证明：
有 T(k) ≤ cn,k < n
则 T(n) ≤ 2c(n/2)+n ＝ cn+n ＝ O(n) 错！
常数,c大于等于 1
代换法 ——例子二（小技巧）
T(n)=2T(n/2)+1
假设,T(1) = Θ(1)
猜测上界函数为,O(n)
证明：
有 T(k) ≤ cn,k < n
则 T(n) ≤ 2c(n/2)+1 ＝ cn+1 怎么办？ O(nlgn)?
加强条件 T(k) ≤ cn-b,其中 b>=0
T(n) ≤ 2(c(n/2)-b)+1=cn-(2b-1) ≤ cn
常数,b大于等于 1/2,c取足够大递归树方法
T(n)=3T(n/4)+cn2
T(n)=T(n/3)+T(2n/3)+O(n)
主方法
递归式形式如下,T(n) = aT(n/b) + f(n),其中
a ≥ 1,b > 1,f(n)是渐近的正函数
主定理：比较 f (n) 和 nlogba:
f (n) = O(nlogba –ε),常数 ε > 0,T(n) = Θ(nlogba)
f (n) = Θ(nlogba lgkn),常数 k ≥ 0,T(n) = Θ(nlogba
lgk+1n)
f (n) = O(nlogba +ε),常数 ε > 0,T(n) = Θ( f (n))
主方法 ——例子
T(n)=9T(n/3)+n
T(n)=T(2n/3)+1
T(n)=2T(n/2)+nlgn
