算法与计算复杂性课程(2)数学基础

《算法与计算复杂性课程(2)数学基础》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学基础•符号说明¢取整函数¢对数¢阶乘•求和¢估计和式的上界•递推方程求解•递推方程中涉及⎣x⎦和⎡x⎤的处理方法1符号说明取整函数⎣x⎦：小于等于x的最大整数⎡x⎤：大于等于x的最小整数性质x-1<⎣x⎦≤x≤⎡x⎤

2、!=2πn()(1+Θ())Stirling公式enn!=o(nn)2n=o(n!),logn!=Θ(nlogn)4求和nn+1kx−1公式∑x=k=0x−1n1∑=lnn+O(1)k=1kn−11n−111例1∑=∑(−)k(k+1)kk+1k=1k=1n−11n−11=∑∑−kk+1k=1k=1n−11n11=∑−∑=1−kknk=1k=25例题kkt−1tt−1例2∑t2=∑t(2−2)t=1t=1kkkk−1tt−1tt=∑t2−∑t2=∑t2−∑(t+1)2t=1t=1t=1t=0kk−1k−1tttkk=∑t2−∑t2−∑2=k2−(2−1)t=1t=0t=0k=

3、(k−1)2+16估计和式的上界方法一：放大法na≤na∑kmaxk=1ak+1≤r,对于一切k≥0,r<1为常数，则akn∞∞kka0a≤ar=ar=∑k∑00∑1−rk=0k=0k=07例题例3估计以下和式的上界nk∑kk=13kk+1ak+11k+12解a=,a=，=≤k3kk+13k+1a3k3kn∞k12k∑k≤∑()333k=1k=1∞12k11≤∑()==13332k=01−38估计和式的界方法二：利用积分例4调和级数求和n1n+1dx∑≥∫=ln(n+1)k1xk=1nn111ndx∑=+∑≤1+∫=lnn+1k=1k1k=2k1x9积分作为上、下界图1调和级

4、数求和的积分近似10例题例5证明logn!=Θ(nlogn)12345n-1nnnlogn!=∑logk≥∫logxdxk=11=loge(nlnn−n+1)=Ω(nlogn)11例题12345nn＋1nn+1logn!=∑logk≤∫logxdx=O(nlogn)k=1212递推方程的求解•递推方程定义•求解方法¢公式法（换元法）¢迭代归纳法（差消法化简）¢递归树¢尝试法¢Master定理13递推方程的定义设序列a,a,…,a,…,简记为{a},01nn一个把a与某些个a（i

5、法1.3Hanoi(A,C,n）1.ifn=1thenmove(A,C)2.elseHanoi(A,B,n−1)3.move(A,C)4.Hanoi(B,C,n−1)递推方程T(n)=2T(n－1)+1T(1)=114常系数线性齐次递推方程标准形：H(n)−a1H(n−1)−a2H(n−2)−⋅⋅⋅−akH(n−k)=0,n≥k,a1,a2,...,ak是常数，ak≠0kk−1特征方程x−a1x−...−ak=0特征根q,q,…,q，12k通解H(n)=cqn+cqn+…+cqn1122kk如果有重根，q是e重特征根，通解对应于根q的部分e−1n(C1+C2n+...+Cen

6、)q整个通解为各个不等的特征根的对应部分之和代入初值确定待定常数例6H(n)+H(n−1)−3H(n−2)−5H(n−3)−2H(n−4)=0H(0)=1,H(1)=0,H(2)=1,H(3)=2特征方程x4+x3−3x2−5x−2=0,特征根−1,−1,−1,2,2nn通解H(n)=(c1+c2n+c3n)(−1)+c42⎧c1+c4=1⎪代初值⎪−c1−c2−c3+2c4=0⎨⎪c1+2c2+4c3+4c4=1⎪⎩−c1−3c2−9c3+8c4=2712解得c1=,c2=−,c3=0,c4=939解为7n1n2nH(n)=(−1)−n(−1)+2939常系数线性非齐次递推

7、方程标准型H(n)−a1H(n−1)−a2H(n−2)−...−akH(n−k)=f(n)H(0)=d0,H(1)=d1,H(2)=d2,...,H(k−1)=dk−1通解为对应的齐次通解加上特解H(n)=H(n)+H*(n)特解的函数形式依赖于f(n)求解的关键是用待定系数法确定一个特解H*(n）实例例7Hanoi塔T(n)=2T(n−1)+1,T(1)=1特解为常数PP=2P+1⇒P=−1特征方程x−2=0特征根2通解T(n)=C2n−1代入初值得C=1解T(n)=2n−1实例：插入排序算法1.4I