知识卡片

普通读书笔记卡 · 3724.b.1

分段求和改进下界

理解等级:中级

逐项用全局最小项估下界可能过弱;先把索引区间切段,可在后半段利用更大的统一下界。

前n个正整数和的后半段已有Θ(n)项且各项Ω(n),从而得到Ω(n²)。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      Splitting summations One way to obtain bounds on a difficult summation is to express the series as the sum of two or more series by partitioning the range of the index and then to bound each of the resulting series. For example, let’s find a lower bound on the arithmetic series , which we have already seen has an upper bound of

    参考来源

    - 位置:《算法导论(第4版)》附录A《求和》(OEBPS/appendix001.xhtml,文本字符[5000,10000))。 - 结论依据:附录A的求和定义、级数性质或界估方法;关键积分夹和图A.1与公式图已核对。 - 原始内容:Splitting summations One way to obtain bounds on a difficult summation is to express the series as the sum of two or more series by partitioning the range of the index and then to bound each of the resulting series. For example, let’s find a lower bound on the arithmetic series , which we have already seen has an upper bound of