算法课程4-math preliminary2.doc

若不是常系数线性递归方程，则需要用生成函数法生成函数法应用举例： 先看一下 A(x)*A(x)即 A2(x)的展开式形状设 A(x)= ，则 A2(x)= * =0nnax0nnax0n(a0+a1x+a2x2+a3x3+…+anxn+…)* (a0+a1x+a2x2+a3x3+…+anxn+…)=a02+(a0a1+a1a0)x+(a0a2+a1a1+a2a0)x2+(a0a3+a1a2+a2a1+a3a0)x3+…+ (a0an+a1an-1+…+an-1a1+ana0)xn+…E.g. 求解下列非线性递归方程 已知 an=a1an-1+a2an-2+ …+an-1a1 (n≥2) 且 a1=1，a 2=1，a 3=2，a 4=5，求 an令 a0=0，则上述方程可写为：a n = a0an+a1an-1+ … +an-1a1+ana0从 2 开始对等式两边分别求级数，则有= (a0an+a1an-1+ … +an-1a1+ana0)*xn2nnxa2设 A(x)= 是数列{a 0, a1,a2,…,an,…}的0nn生成函数（幂函数形式） ，则有A(x)-a1x-a0=(A(x))2-(a1a0+a0a1)x-a20 ，整理得(A(x)) 2-A(x)+x=0。

令 z=A(x)，则有 z2-z+x=0求解此关于 z 的一元二次方程式，得 A(x)= z=(1 )/2x41即 A(x)应为 1/2 /2 ∵ = ，x41x41112)(nnnC即 的幂级数展开式通项系数为 bn=-x41，a n= bn/2，而 an 为正数，∴ 中符号取为负，n2C12 x41于是有A(x)=1/2- /2，a n= （ 定义为 1） x41Cn120此数称为 Catalan 数（有很多应用均涉及此数） 算法分析中用到的其它一些常用数学方法：1、求和转化为求积分：eg1：已知㏒n!=㏒n+ ㏒(n-1)+…+㏒2+㏒1= njj1log求㏒n!的不含∑的表达式如下图，在区间[1,n+1]中，曲线 y=㏒x 之下的面积为 ，1lognxd而㏒n!（ ）则等于njj1log曲线 y=㏒ x 之下 n-1 个小矩形的面积之和∴㏒n! 成立（n-1 个小矩形均左移一个单位，nx1l则可覆盖区间[1,n]上的曲线下的面积 ） 于是求和就可转化为求积分用分部积分法，有 =(xlnx-x)| = n㏑n – n + 1, nxd1l 1且㏒x=㏒e* ㏑x (由 x=elnx)，∴㏒n!＞ =㏒e (n㏑n-n+1)=n㏒n-n㏒e+㏒e，nd1log㏒n!＜ =(n+1)㏒(n+1)-(n+1)㏒e+㏒e,1lnx∵n 充分大时上述两项主部均为 n㏒n，∴㏒n!= (n㏒n)。

e.g.2：类似的有： ≤ ≤n0kdxnjk11nkdx∴ ≤ ≤ , ∴ =( )11knknjk11)(1kknjk1k1eg3： =1+ ≤1+ =1+㏑n，njj1njj21nxd1另外 ≥ ＝㏑(n＋1)，∴ ＝( ㏒n)nj11nxd njj1eg4：著名的 Stirling 公式 n!≈ )2en也是利用了上述的积分办法（证明较复杂，省略有兴趣可参看卢开澄书 ）2、代入法求解：e.g. T(n)= 设 n=2k（因此 k=㏒n ） ，2log)2/(1ncnTd于是有：T(n) =2T(n/2) +cn*㏒n =2(2T(n/22)+c(n/2)*㏒(n/2))+cn*㏒n=22T(n/22)+cn*㏒(n/2)+cn* ㏒n=……=2kT(n/2k)+cn(㏒(n/2 k-1)+㏒ (n/2k-2)+……+㏒(n/2 0))=dn+cn(㏒2 1+㏒2 2+……+㏒2 k)=dn+cn =dn+cn =dn+cn +cnkj1 2)1(k 2logn2logn若 n2k，则必有 k，使得 2k-1 0 且一般为正整数，此类方程可（粗略地）按 f(n) ( )分为三种情况：aLogbn（注意: 递归方程 T(n)=a*T(n/b)的齐通解为 c* ，aLogbnc 为待定常数）主定理: (参见 Corman 书 P76)1)若有 ε> 0, 使 f(n)=O( ) (aLogbn(即 f(n)的量级多项式地小于 的量级), aLogb则 T(n)=  ( )。

aLogbn2)若 f(n)= ( )aLogb(即 f(n)的量级等于 的量级), aLogbn则 T(n) =( )aLogbn若 f(n)= ( ), 则 T(n)=( )aLogbnk aLogbnnk13)若有 ε>0, 使 f(n)=( ) aLogb(即 f(n)的量级多项式地大于 的量级), abLogn且满足正规性条件：存在常数 c<1, 使得对所有足够大的 n，有 a*f(n/b)c*f(n), 则 T(n)=(f(n))正规性条件的直观含义: 对所有足够大的 n，a 个规模为 n/b 的子问题的分解准备与再综合所需要的时间总和，严格小于原规模为 n 问题的分解准备与综合所需的时间因此一般来说，对于时间复杂度满足递归关系T(n)=a*T(n/b)+f(n)的算法，只需比较 f(n)与 的量级大小，aLogbn算法的时间复杂度总是与量级大的那个相同（即小的那个可以忽略） ；若 f(n)与 的量级相同（或只差 ） ，aLogbn nLogk则算法的时间复杂度为 f(n)* 注意：以上三类情况并没有包括所有可能的 f(n):a) f(n)介于 1),2)之间，即 f(n)小于、但不是多项式地小于 abLognb) f(n)介于 2),3)之间，即 f(n)大于、但不是多项式地大于 abLogn当 f(n)不满足 1),2),3)时，只能采用其他方式求解。

主定理的证明思路（CormanP76 有详细证明）对 T(n)=a*T(n/b)+f(n) 一类的递归方程：当 时，用代入法、并利用等式kbn ,logloganbba以及 T(1)为常数，可得： )()()()()( log10log nnbnfanT ajkjja bb （令 ）)()(10jkjjbnfag1、当 时，则有 ，)()(logabnnf ))()( (logajj bbnf将该等式代入 中的各项，)(ng可得到一个几何级数的求和式，化简该式后可得 )()(logabng2、当 时，则有 ，)()(logabnnf ))()( logajj bnbf将该等式代入 中的各项，则由于)(= =10kjja)(logajbnabnlog10log)/(kj jab nnbabloglog（ 是一个各项均为 1 的特殊级数，而 ）10log)/(kj jab nkblog由此即可得 )log()(lognnbab3、若 （c<1，正规性条件） ，)()(cfbnaf则利用代入法可得(0jk-1)，)()( nfcbnfajjj 将该不等式代入 则有)(g（∵c<1） )()1)()()()( 010 nfcnfcnffcngjjkjj 又由 的定义知 ，)( )()(fg即有 ，所以 。

)()(nfng )(nfn由主定理的结论，还可以获得一些关于算法改进的启示：当 T(n)=( )时，即当 的量级高于 f(n)的量级时，aLogbnaLogbn的量级在算法的时间复杂度中起主导作用aLogb因而此时首先应当考虑使㏒ b a 的值变小，而暂时无须考虑如何改善 f(n)，即此时要考虑减小 a（子问题个数）且使 b 不变（n/b 为子问题规模） ，或增大 b（减小子问题规模）而使 a 不变也就是说，此时的重点应考虑改进子问题的分解方法，暂不必考虑改进子问题组合时的处理当 f(n)的量级高于或等于 的量级时，aLogbn则 f(n)的量级在算法的时间复杂度中起主导作用因而此时首先应当考虑把 f(n)的量级往下降，即此时应着重改善子问题分解、组合时的处理方法，减少该部分工作的处理时间 f(n)思考题：1.证明：n 个矩阵连乘，加括号的方法数是 n 阶 Catalan 数： n112C2.证明：把 边凸多边形划分成 n-2 个三角形的)3(n方法数是 n-1 阶 Catalan 数： 1n24nC3.设有 n 个实数 a1

试证明：以 a1,a2,…,an 为节点构成的不相同的n 节点二叉树的棵数为 n+1 阶 Catalan 数 1nnC24.证明：n 个数据元素进出栈的方法数是 n+1 阶 Catalan 数 1nnC25.若 T(n)=kxbcbnaTd且常 数 2)/()(用代入法求:a bx 时的 T(n)的表达式（越精确越好）6.设 并利用代入法、函数变形法，及等式 ,kbn ,logloganbba证明齐次方程 的解为 这里 )()(bnaT,logabdn)1(Td。