知识卡片

普通读书笔记卡 · 3724.d

调和数增长为对数级

理解等级:初级

第n个调和数H_n是1、1/2、…、1/n之和,随n增长为Θ(log n)。

它虽每项递减,无限级数仍发散;逐项比值小于1不等于存在统一小于1的几何公比。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 附录A 求和 · 查看原书依据

      Harmonic series For positive integers n, the nth harmonic number is Inequalities (A.20) and (A.21) on page 1150 provide the stronger bounds Integrating and differentiating series Integrating or differentiating the formulas above yields additional formulas. For example, differentiating both sides of the infinite geometric

    参考来源

    - 位置:《算法导论(第4版)》附录A《求和》(OEBPS/appendix001.xhtml,文本字符[0,5000))。 - 结论依据:附录A.1“Harmonic series”及原书公式图 Art_P1540.jpg、Art_P1541.jpg(式A.8–A.10):正整数 n 的 H_n=∑_{k=1}^n 1/k=ln n+O(1),且 ln(n+1)≤H_n≤ln n+1,因此为 Θ(log n)。附录A.2另以调和级数为反例说明相邻项比值各自小于1不足以给出统一几何公比。 - 原始内容:Harmonic series For positive integers n , the n th harmonic number is Inequalities (A.20) and (A.21) on page 1150 provide the stronger bounds Integrating and differentiating series Integrating or differentiating the formulas above yields additional formulas. For example, differentiating both sides of the infinite geometric