**********************算法设计与分析福建师范大学算法设计与分析福建师范大学算法设计与分析——数学预备知识数学预备知识主要内容：介绍算法设计与分析中必需的数学知识。数学预备知识一.算法分析中相关的数学工具（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.递归方程(