知识卡片
分段求和改进下界
逐项用全局最小项估下界可能过弱;先把索引区间切段,可在后半段利用更大的统一下界。
前n个正整数和的后半段已有Θ(n)项且各项Ω(n),从而得到Ω(n²)。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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