知识卡片

普通读书笔记卡 · 5654.c.1.a.1

顺序相加嵌套按边界求和

理解等级:中级

顺序执行的工作合计成本;独立重复固定次数的嵌套循环可以相乘。若内层次数依赖外层,就要先写每轮实际次数再求和,而不是看见两层就直接判平方。

对于系数固定、非负成本的有限多项式,足够大规模下最高阶项主导增长,可省略固定倍数和低阶项。这个渐近简化不说明小输入的真实耗时顺序。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      可以总结出以下计数简化技巧。 1. 忽略 中的常数项。因为它们都与次、5 +无关,所以对时间复杂度不产生影响。 1 2. 省略所有系数。例如,循环 次等,都可以简化记为 次,因为 前面的系数对时间复 杂度没有影响。 3.

    参考来源

    - 位置:《Hello 算法--Go版本》第02章《复杂度分析》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/1.html;spine 0,归一字符[26414,26524)) - 结论依据:原文三种简化及最高阶主导,在独立边界下保留乘法,修正无条件嵌套乘法。 - 原始内容:可以总结出以下计数简化技巧。 1. 忽略 中的常数项。因为它们都与次、5 +无关,所以对时间复杂度不产生影响。 1 2. 省略所有系数。例如,循环 次等,都可以简化记为 次,因为 前面的系数对时间复 杂度没有影响。 3.