知识卡片

普通读书笔记卡 · 3724.j

单调函数可用积分夹和

理解等级:高级

当f单调时,求和可视为单位宽矩形面积,用左右错开的积分夹住。

递增与递减情形的不等号方向不同,须按图A.1和求和起止点核对;例如调和和可据递减情形得到对数级界。

这张卡片看不懂?

已有反馈 · 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