算法导论 读书笔记

《算法导论》读书笔记_附录A习题解答 学习C C++ 资料A.2-2求和D∑的渐近上界gnk Ig∑[1≤∑(+1)=n∑(5)+∑1=2-1+gn+1=2+1n故渐近上界是O(m)A.2-3通过分割求和证明第n个调和数是9(gm)lgn」-12-1∑k∑∑么=022+;+2可n-1∑1+22-1+1∑故取得下界g2(1gn)A2-4通过积分求》k的近似值。=Cm∈∑厂e=4∑(n+1)A.2-5题略。为了保证被积函数在积分域上都连续思考题A-1求和的界求下列和式的渐近确界。假设≥0,s≥0都是常量。a)∑k/,得到界为∑Ig hgn」∑k≤∑∑g(2+)=0∑(2×lg(2+2-1+∑(2×(+1)lg∑(2×(gn+1)gnl∑(2)=0根据此式得到上界:∑!g"k≥∑∑lg"(2+j)+g(2l∑(2×1g2(2)+(g°m)Ig n-2∑(2×)+0(g=0≥2m=2×(gn-2)°+(1gn)02=×lg4)+g(lgn-2)+O(lg。m)=e(nIg r故得到下界Q(nlg n故据此得到确界((2∑k"lgkl1n」21∑klgk≤∑∑[(2+i)"g(2+k=1Ig≤∑[(2+2-1+1)xg(2+2-1+1)lg n∑[((lo n≤22×(lg7+1)0g2×∑1=0故得到上界:O(nlgm)∑klgk≥∑∑[(2+)1g(2+)+(gn-1)1g(Lm-1)∑[(2)xg(2)]+(lg n-=2×∑(2×2lgn2)°×E(nlg n)故得到下界:9(mlgm)因此得到确界(nlm)