知识卡片

普通读书笔记卡 · 3724.c

几何级数由公比控制

理解等级:中级

几何级数各项按固定公比x递推。x≠1时,前m+1项的和为

1+x+x²+⋯+xᵐ = (1−xᵐ⁺¹)/(1−x)。

推导只需令S为左侧,计算S−xS,所有中间项相消,得到S(1−x)=1−xᵐ⁺¹。若x=1,和直接是m+1。

当|x|时,xᵐ⁺¹趋于0,无限和收敛到1/(1−x);若|x|≥1,不能借用这个递减几何级数的有限上界。

递归层成本若形成固定比率,先核对公比范围再用公式。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      Geometric series For real x ≠ 1, the summation is a geometric series and has the value The infinite decreasing geometric series occurs when the summation is infinite and |x| < 1: If we assume that 00 = 1, these formulas apply even when x = 0. Harmonic series For positive integers n, the nth harmonic number is Inequalities

    参考来源

    - 位置:《算法导论(第4版)》附录A《求和》(OEBPS/appendix001.xhtml,文本字符[0,5000))。 - 结论依据:附录A的求和定义、级数性质或界估方法;关键积分夹和图A.1与公式图已核对。 - 原始内容:Geometric series For real x ≠ 1, the summation is a geometric series and has the value The infinite decreasing geometric series occurs when the summation is infinite and | x | < 1: If we assume that 0 0 = 1, these formulas apply even when x = 0. Harmonic series For positive integers n , the n th harmonic number is Inequalities