算法设计与分析-3求和运算

《算法设计与分析-3求和运算》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析谭守标安徽大学电子学院2007.9第三章求和运算3.1求和公式的性质3.2和式求界3.1求和公式的性质有限和：（求和序数为非整数时默认为其底函数）无穷和：即发散、收敛、绝对收敛3.1求和公式的性质线性性质（对无穷收敛级数也成立）3.1求和公式的性质算术级数几何级数无穷下降几何级数：（

2、x

3、<1）积分级数与微分级数3.1求和公式的性质调和级数套叠级数和例：3.1求和公式的性质积3.2和式求界数学归纳法例：证明的界是0(3n).即证明存在常数c满足：n=0时c≥1即可。假设界对n成立，则n+1时：

4、只需(1/3+1/c)≤1即c≥3/2即可。3.2和式求界数学归纳法（续）反例：证明n=1时显然成立。假设界对n成立，则n+1时：原因：被O隐藏的常数随n增长，不再是是常数。3.2和式求界对项限界最大项限界对级数设则：3.2和式求界对项限界（续）几何级数限界给定级数，设对所有k≥0，有ak+1/ak≤r(r<1为常数)则：ak≤a0rk例：可对求界。而不能求的界。3.2和式求界分解和式例：利用和式分解：3.2和式求界分解和式（续）若和式中的各项ak独立于n，即对任意常量k0>0，满足：（即可忽略初始的几项）

5、3.2和式求界分解和式（续）例：求的界当n≥3时有：故：3.2和式求界分解和式（续）例（更复杂）：求的界思路：把域1到n分解成lgn段，每段上界为13.2和式求界积分近似公式（续）对单调增函数：3.2和式求界积分近似公式（续）3.2和式求界积分近似公式（续）可看出对单调增函数：同理对单调减函数：3.2和式求界积分近似公式（续）例：调和函数的紧确界：作业证明由一个常数从上方限界。TheEndThankyou!