知识卡片

普通读书笔记卡 · 3724.i

逐项最大值给粗上界

理解等级:中级

n项非负和可用n乘最大项给上界,求值快但可能很松。

若项按固定小于1的比率衰减,更适合用几何级数界;选界法时应比较它是否保留了项随索引变化的结构。

这张卡片看不懂?

已有反馈 · 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