知识卡片
顺序相加嵌套按边界求和
顺序执行的工作合计成本;独立重复固定次数的嵌套循环可以相乘。若内层次数依赖外层,就要先写每轮实际次数再求和,而不是看见两层就直接判平方。
对于系数固定、非负成本的有限多项式,足够大规模下最高阶项主导增长,可省略固定倍数和低阶项。这个渐近简化不说明小输入的真实耗时顺序。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 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.