《离散数学递推方程与生成函数》由会员分享，可在线阅读，更多相关《离散数学递推方程与生成函数（41页珍藏版）》请在金锄头文库上搜索。
1、第第1010章章 递推方程与生成函数递推方程与生成函数1第第10章章 递推方程与生成函数递推方程与生成函数10.1 递推方程及其应用递推方程及其应用10.2 生成函数及其应用生成函数及其应用10.3 指数生成函数及其应用指数生成函数及其应用10.4 Catalan数与数与Stirling数数210.1 递推方程及其应用递推方程及其应用10.1.1 递推方程的定义及实例递推方程的定义及实例10.1.2 常系数线性齐次递推方程的求解常系数线性齐次递推方程的求解10.1.3 常系数线性非齐次递推方程的求解常系数线性非齐次递推方程的求解10.1.4 递推方程的其他解法递推方程的其他解法10.1.5 递
2、推方程与递归算法递推方程与递归算法3递推方程的定义递推方程的定义定义定义10.1 设序列设序列 a0, a1, , an, , 简记为简记为 an . 一个把一个把 an 与与某些个某些个ai (i028实例实例解解 H(k) = 2 H(k1) + 2k1 H(1) = 1 令令 H*(k) = P1k2k + P2 , 解得解得 P1=P2=1 H*(k) = k2k + 1通解通解 H(k) = c 2k + k2k + 1 代入初值得代入初值得 c = 1 H(k) = 2k + k2k +1 W(n) = n log n n + 1 例例1414 归并排序归并排序29迭代归纳法迭代归
3、纳法归并排序归并排序例例1530迭代归纳法迭代归纳法错位排列错位排列例例16 Dn = (n1)(Dn1 + Dn2) 解：解：31差消法差消法化简递推方程化简递推方程例例1732积分近似积分近似33递归树递归树二分归并排序二分归并排序T(n)n-1T(n/2) T(n/2)n/2-1 n/2-1T(n/4) T(n/4) T(n/4) T(n/4)n/4-1 n/4-1 n/4-1 n/4-1 .1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 T(n) = nk (1+2+2k 1) = nk (2k 1) = n log n n + 1 n 1n 2n 4. n 2k 1k
4、层层34(1) T(n)=C, 左左边=O(1)尝试法尝试法例例18 (2) T(n)=cn, 左左边=cn, 35尝试法尝试法(续续)(3) T(n)=cn2, 左左边=cn2(4) T(n)=cnlogn , 左左边=cnlogn 36积分近似积分近似37分治策略与递归算法分治策略与递归算法n为输入入规模，模，n/b为子子问题输入入规模，模，a为子子问题个数，个数，d(n)为分解及分解及综合的代价合的代价38分治策略与递归算法分治策略与递归算法(续续)(1) d(n)=c 实例：例： 二分搜索二分搜索 W(n) = W(n/2) + 1 a = 1, b = 2, d(n) = c W(n
5、) = O(logn) 39分治策略与递归算法分治策略与递归算法(续续) (2) d(n)=cn 实例：例：归并排序并排序 W(n) = 2W(n/2) + n 1 a = 2, b = 2, d(n) = O(n), W(n)= O(nlogn) 40实例实例位乘问题位乘问题位乘问题：位乘问题：X,Y 为为 n 位二进制数，位二进制数，n=2k, 求求 XY 一般方法：一般方法：W(n)= O(n2)分治法：令分治法：令X = A2n/2+B, Y = C2n/2 +D, 则则 XY = AC 2n + (AD+BC)2n/2 + BD W(n)= 4 W(n/2) + cn W(1)= 1 a = 4，b = 2, W(n)= O(nlog4)= O(n2)变换：变换：AD + BC = (A B)(D C) + AC + BD W(n) = 3 W(n/2) + cn W(1)= 1 a = 3，b = 2, W(n)= O(nlog3)= O(n1.59) 41
