算法数学基础

1、数学基础数学基础p符号说明符号说明n取整函数取整函数n对数对数n阶乘阶乘p 求和求和n估计和式的上界估计和式的上界p递推方程求解递推方程求解p递推方程中涉及递推方程中涉及 x 和和 x 的处理方法的处理方法 1符号说明符号说明2 abnbanabnbannnn,22取整函数取整函数 x ：小于等于：小于等于x的最大整数的最大整数 x ：大于等于：大于等于x 的最小整数的最小整数性质性质 x-1 x x x x+13ncnnannnnnnnnlkankkbbloglog)log(logloglog)(loglog)log(lg,loglogloglog22 性性质质：符符号号：对数函数对数函数换

2、底4阶乘阶乘 )1(1()(2!nennnn n! = o(nn) 2n= o(n!), log n! = (n log n)Stirling公式公式5求和求和 nknnkkOnkxxx110)1(ln111例例1 1 nknknknknknknkkkkkkkk211111111111111111)111()1(1公式公式 例题例题612)1()12(22222)1(222)22(2101011011111111 kkkkttkttkttkttkttkttktttkttkttkktttttttt例例2 2估计和式的上界估计和式的上界7rararaarkraanaakkkknkkkknkk 11

3、, 0,00000011max为常数，则为常数，则对于一切对于一切方法一：放大法方法一：放大法 例题例题8例例3 3 估计以下和式的上界估计以下和式的上界 nkkk13 3213131,3111 kkaakakakkkkkk， 1321131)32(31)32(313011 kkkknkkk 解解估计和式的界估计和式的界9 方法二：利用积分方法二：利用积分 例例4 4 调和级数求和调和级数求和nnknknknnxdxkknxdxk1211111ln11111)1ln(1 积分作为上、下界积分作为上、下界10图图1 调和级数求和的积分近似调和级数求和的积分近似1+1/3+1/4.+1/n+1/3

4、+1/4.+1/n例题例题11)log(!lognnn 例例5 5 证明证明 nnkxdxkn11loglog!log 1 2 3 4 5 n-1 n )log()1ln(lognnnnne log2+log3+.+logn12)log(loglog!log121nnOxdxknnnk 1 2 3 4 5 n n1 例题例题递推方程的求解递推方程的求解p递推方程定义递推方程定义p求解方法求解方法n公式法（换元法）公式法（换元法）n迭代归纳法（差消法化简）迭代归纳法（差消法化简）n递归树递归树n尝试法尝试法nMaster定理定理13递推方程的定义递推方程的定义14设序列设序列 a0, a1, ,

5、 an, , 简记为简记为an, 一个把一个把 an与某些个与某些个 ai（i0 and xAi 5. do Ai+1Ai 6. ii 1 7. Ai+1x 192)1()(0)1( 1)1()( nnnWWnnWnW最坏实例：归并排序实例：归并排序算法算法1.5 MergeSort(A,p,r) /* 归并排序数组归并排序数组Ap.r 1. if pr 2. then q(p+r)/2 3. MergeSort(A,p,q) 4. MergeSort(A,q+1,r) 5. Merge(A,p,q,r)20 0 (1) 1 /2)(2 )(WnnWnW n-1为两组分别排序完成的组合并的操作

6、次数换元法换元法例例8令令 H*(k) = P1k 2k +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 0)0(12)1(2)(0 (1) 21 /2)(2 )(HkHkHWnnnWnWkk迭代归纳法迭代归纳法22 0)1( 1)1()(WnnWnW例例9 用迭代归纳法求解以下递推方程用迭代归纳法求解以下递推方程: : W(n) = W(n 1) + n 1= W(n 2) + n 2 +

7、 n 1 = W(n 2) + (n 2) + (n 1) = = W(1) + 1 + 2 + + (n 2) + (n 1) = 1 + 2 + + (n 2) + (n 1) (代入初值代入初值W(1)=0) = n(n 1)/2 用归纳法验证用归纳法验证差消法：化简递推方程差消法：化简递推方程230)1(2, 1)(2)(11 TnniTnnTni 212112)1()1()(2)1()1()(2)(nininniTnTnnniTnnT相减并化简得相减并化简得 22)1()1()( nnTnnnT例例10 求解递推方程求解递推方程24由叠代得由叠代得 )1()31.111(2)1(2)

8、1(31.122121)(OnnOTnnnnnT T(n)=O(nlog n) nnnnnTnnT)1(212)1(1)( 迭代归纳法求解迭代归纳法求解25)(log2ln)1ln(ln131.1111212nOnxdxxnnnn 估计和式的阶估计和式的阶递归树法：迭代的树形表示递归树法：迭代的树形表示262)2(2)(nnTnT 222222222241)4()4()4()4(21)2()2(nnnnnnnnnn log n层层 (n2) 例例1111 求解求解 1+1/2。收敛为常数27例例1212nnTnTnT )32()3()( nnnnnnnnnn9492929323 log c n

9、 层层 (n log n)递归树求解实例递归树求解实例左右层数不一样28Master定理定理 )()(),()/(1, 0),()(. 3)log()(),()(. 2)()(, 0),()(1.),()/()()(,)(1, 1logloglogloglognfnTncfbnafncnnfnnnTnnfnnTnOnfnfbnaTnTnTnfbaaaaaabbbbb 那么那么有有所有的充分大的所有的充分大的和和且对于某个常数且对于某个常数那么那么那么那么则有以下结果：则有以下结果：为非负整数为非负整数为函数为函数为常数，为常数，设设 29证明证明)()()1()()(.)()(.)()()()

10、()()()()()(1log0log10log11222jnjjajkjjnkkkkbnfanbnfaTanfbnafbnfabnTanfbnafbnTanfbnfbnaTanfbnaTnTbbb k=logbn30Case 1)()()11()()()()(loglogloglogloglog1log0logloglog1log0log10logaaanaanjjaaajnjjakjjjabbbbbbbbbbbbbnnOnbbnOnbnOnbnaOnbnfannT )()(log abnOnf分母常数扔掉，换底公式31Case 2)log()()()()(log1log0logloglog

11、1log0log1log0lognnaannbnanbnfannTanjjjaaajnjjajnjjabbbbbbbbb )()(log abnnf 32Case 3 )()(1)(11)()()()()()()(loglog1log0log1log0log1log0log aanjjanjjajnjjabbbbbbbbnnfcnfcnfncnfnnfcnncfbnafbnfannT)()(),()(logncfbnafnnfab C小于一则合式收敛为常数后者阶高于前者33例例1313 nnTnT )3/(9)()()(),()(,)(, 3, 9219log29log33nnTnOnfnnn

12、nfba )()(, 0),()(loglogaabbnnTnOnf 那那么么 Master定理的应用：定理的应用： Case 1 34Master定理应用：定理应用：Case 2)log()(),()(, 1, 1)(, 2/3, 11log01log2/32/3nnTnnfnnnfba 1)3/2()( nTnT例例1414 )log()(),()(loglognnnTnnfaabb 那那么么35Master定理应用：定理应用：Case 3)log()(, 4/3),(log)4/3()4/log()4/(3)/(, 2 . 0),()(),(,log)(, 4, 33log793. 03

13、log44nnnTncncfnnnnbnafnnfnOnnnnfba 充充分分大大)()(),()/(1, 0),()(lognfnTncfbnafncnnfab 那那么么有有充充分分大大的的和和所所有有且且对对于于某某个个常常数数 nnnTnTlog)4/(3)( 例例1515 递推方程中递推方程中 x 和和 x 的处理的处理36先猜想解，然后用数学归纳法证明先猜想解，然后用数学归纳法证明例例16 16 估计以下递推关系的阶估计以下递推关系的阶 1)1()(2)(2 TnTnTn 根据根据 nnTnT )2(2)( T(n) = O(n log n)猜想原递推方程的解的阶是猜想原递推方程的解的阶是O(n log n)证明：证明：用数学归纳法用数学归纳法T(