知识卡片
调和数增长为对数级
第n个调和数H_n是1、1/2、…、1/n之和,随n增长为Θ(log n)。
它虽每项递减,无限级数仍发散;逐项比值小于1不等于存在统一小于1的几何公比。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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