算法设计与分析第2章数学预备知识

算法设计与分析——数学预备知识数学预备知识主要内容：介绍算法设计与分析中必需的数学知识。

数学预备知识一.算法分析中相关的数学工具

（2.1~2.7）集合、关系、函数、对数和证明方法（自行复习）2．底函数和顶函数(2.4)

设x为实数。●底函数：小于或等于x的最大整数。●顶函数：大于或等于x的最小整数。例：=3=-4=4=-3数学预备知识一.算法分析中相关的数学工具

（2.1~2.7）2．底函数和顶函数(2.4P45)●相关性质：

(1)=x,x为整数

(2)，x为实数

(3)定理2.1设f(x)是单调递增连续函数，使得若f(x)是整数，则x是整数。那么，且●定理2.1的应用(P45)数学预备知识一.算法分析中相关的数学工具

（2.1~2.7）3.阶乘和二项式系数（排列和组合）●Stirling公式：n!●关于二项式系数的有关公式：

●帕斯卡三角形（图2.1P48）

数学预备知识一.算法分析中相关的数学工具

（2.1~2.7）4.鸽巢原理(P48)

●定理2.3(鸽巢原理)如果把n个球分别放在m个盒子中，那么：

(1)存在一个盒子，必定至少装个球；

(2)存在一个盒子，必定最多装个球；●例2.13(P48)

数学预备知识一.算法分析中相关的数学工具

（2.1~2.7）5.和式(2.7P48)

●和式的不同表示法：

其中,f(1),f(2),…,f(n)是1,2,…,n的一个排列。例如，上述公式在简化和变换含和式的表达式时是很有用的。另外还可变换和式的下标（见例2.14）。数学预备知识一.算法分析中相关的数学工具

（2.1~2.7）5.和式

●常用的级数（P49）数学预备知识一.算法分析中相关的数学工具

（2.1~2.7）6.求和的积分近似可利用积分得到一些和式值的上下界，从而得到和式的近似值。利用定积分的几何性质，可得如下结论。（见图2.2,2.3）●若f(x)是单调递减的，则若f(x)是单调递增的，则

●例2.16数学预备知识二.递归方程（递推式）的解法

(2.8)

递归算法的时间复杂性满足递归方程。例1:二分查找算法的最坏情况下时间复杂性满足如下递归方程：

(1)

数学预备知识二.递归方程（递推式）的解法

(2.8)

例2:Hanoi塔问题的递归算法的时间复杂性满足如下递归方程：

(2)

数学预备知识二.递归方程（递推式）的解法

(2.8)递推法:利用递归关系反复递推展开，直至初始值为止。

●例1.递归方程(2)●例2.递归方程(1)

递推法适用于解递归关系较简单的递归方程。数学预备知识二.递归方程（递推式）的解法

(2.8)2.线性齐次递归方程的求解(1)k阶线性齐次递归方程：（简称齐次方程）

f(n)=a1f(n-1)+a2f(n-2)+…+akf(n-k)(1)

其中，k≤n,ai为常数，i=1,2,…,n，ak≠0。●齐次方程的特征方程：

xk-a1xk-1-a2xk-2-…-ak-1x-ak=0●齐次方程的特征根：其特征方程的根。要解k阶齐次方程需要k个初始条件。数学预备知识二.递归方程（递推式）的解法

(2.8)2.线性齐次递归方程的求解(2)齐次方程的通解●设r为齐次方程(1)的一个特征根，令f(n)=rn,则

f(n)为齐次方程(1)的一个特解。

数学预备知识●齐次方程(1)的通解：设齐次方程(1)的k个特征根为r1,r2,…,rk

。若r1,r2,…,rk互不相同，则

f(n)=c1r1n+c2r2n+…+ckrkn

若齐次方程(1)有m个重特征根ri=ri+1=…=ri+m-1,则f(n)=c1r1n+…+ci-1ri-1n+(ci+ci+1n+…+ci+m-1nm-1)rin+ci+mri+mn+…+ckrkn

其中，c1,c2,…,ck为待定常数，由齐次方程(1)的k个初始条件确定。数学预备知识二.递归方程（递推式）的解法

(2.8)2.线性齐次递归方程的求解(3)齐次方程的求解步骤

1）求出齐次方程的所有特征根。

2）构造通解的一般形式，系数待定。

3）将通解代入初始条件，得到一个关于系数的线性方程组。

4）解该线性方程组得所有系数，代入通解得齐次方程的解。数学预备知识二.递归方程（递推式）的解法

(2.8)2.线性齐次递归方程的求解(4)例子(P53)

例2.18

例2.19

例2.20数学预备知识二.递归方程（递推式）的解法

(2.8)3.非齐次递推关系的求解一般来说没有容易的办法处理非齐次递推关系。例2.21例2.22数学预备知识二.递归方程（递推式）的解法

(2.8)4.一类特殊递归方程的求解用分治法解题时，分治算法的时间复杂性常满足如下形式的递归方程：其中，a,c为正整数，d为非负常量，g(n)为非负函数。数学预备知识二.递归方程（递推式）的解法

(2.8)4.一类特殊递归方程的求解解的一般形式：（设n=ck）

其中，称为方程的齐次解，称为方程的特解。(关于这个解的推导可采用更换变元法)

数学预备知识二.递归方程（递推式）的解法

(2.8)4.一类特殊递归方程的求解g(n)=bnx(b,x为非负常量)情况下的解：

其中，n=ck。（引理2.1P57）其中，n为任意正整数。（定理2.5P58）

订正定理2.5数学预备知识二.递归方程（递推式）的解法

(2.8)4.一类特殊递归方程的求解g(n)=b(b为非负常量)情况下的解：(x=0的情况)

其中，n=ck

。其中，n为任意正整数。

数学预备知识二.递归方程（递推式）的解法

(2.8)4.一类特殊递归方程的求解g(n)=bn(b为非负常量)情况下的解：(x=1的情况)其中，n=ck

。（推论2.2P58）其中，n为任意正整数。

数学预备知识二.递归方程（递推式）的解法

(2.8)4.一类特殊递归方程的求解例：求下列递归方程的解：设f(1)=1(1)f(n)=4f(n/2)+n(2)f(n)=4f(n/2)+3n2(3)f(n)=4f(n/2)+n3

数学预备知识二.递归方程（递推式）的解法

(2.8)4.一类特殊递归方程的求解

g(n)为其它函数情况下的解