知识卡片
单调函数可用积分夹和
当f单调时,求和可视为单位宽矩形面积,用左右错开的积分夹住。
递增与递减情形的不等号方向不同,须按图A.1和求和起止点核对;例如调和和可据递减情形得到对数级界。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 附录A 求和 · 查看原书依据
Approximation by integrals When a summation has the form , where f (k) is a monotonically increasing function, you can approximate it by integrals: Figure A.1 justifies this approximation. The summation is represented as the area of the rectangles in the figure, and the integral is the blue region under the curve. When f (k
参考来源
- 位置:《算法导论(第4版)》附录A《求和》(OEBPS/appendix001.xhtml,文本字符[5000,10000))。
- 结论依据:附录A.2“Approximation by integrals”、图A.1及原书公式图 Art_P1597.jpg–Art_P1601.jpg(式A.18–A.21):对整数 m≤n,f 在所涉区间单调递增时,∫_{m−1}^n f(x)dx≤∑_{k=m}^n f(k)≤∫_m^{n+1}f(x)dx;单调递减时两侧积分方向互换,即 ∫_m^{n+1}f(x)dx≤和≤∫_{m−1}^n f(x)dx。取 f(x)=1/x、m=1,得到 ln(n+1)≤H_n≤ln n+1(上界单独拆出首项以避开 x=0)。
- 原始内容:Approximation by integrals When a summation has the form , where f ( k ) is a monotonically increasing function, you can approximate it by integrals: Figure A.1 justifies this approximation. The summation is represented as the area of the rectangles in the figure, and the integral is the blue region under the curve. When f ( k