知识卡片
逐项最大值给粗上界
n项非负和可用n乘最大项给上界,求值快但可能很松。
若项按固定小于1的比率衰减,更适合用几何级数界;选界法时应比较它是否保留了项随索引变化的结构。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 附录A 求和 · 查看原书依据
if we let amax = max {ak : 1 ≤ k ≤ n}, then The technique of bounding each term in a series by the largest term is a weak method when the series can in fact be bounded by a geometric series. Given the series , suppose that ak+1/ak ≤ r for all k ≥ 0, where 0 < r < 1 is a constant. You can bound the sum by an infinite
参考来源
- 位置:《算法导论(第4版)》附录A《求和》(OEBPS/appendix001.xhtml,文本字符[5000,10000))。
- 结论依据:附录A的求和定义、级数性质或界估方法;关键积分夹和图A.1与公式图已核对。
- 原始内容:if we let a max = max { a k : 1 ≤ k ≤ n }, then The technique of bounding each term in a series by the largest term is a weak method when the series can in fact be bounded by a geometric series. Given the series , suppose that a k +1 / a k ≤ r for all k ≥ 0, where 0 < r < 1 is a constant. You can bound the sum by an infinite