知识卡片
代入证明应显式写常数
在归纳假设里只写 T(n)=O(n) 会隐藏可变的常数,使 T(n)≤cn+Θ(n) 被误当成 T(n)≤cn。
代入法应写明同一个 c、起始 n₀ 和待证的精确不等式;最后一步必须回到该不等式,不能只得到相同量级。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第4章 分治策略 · 查看原书依据
When using the substitution method, or more generally mathematical induction, you must be careful that the constants hidden by any asymptotic notation are the same constants throughout the proof.
参考来源
- 位置:《算法导论(第4版)》第 4 章 4.3–4.4 节(`OEBPS/chapter004.xhtml`,文本字符 [40000, 45000))。
- 结论依据:4.3 节指出 cn+Θ(n) 不能推成 cn;归纳假设中的渐近记号会混淆常数,故应固定 c、n₀ 并逐步验证精确不等式。
- 原始内容:When using the substitution method, or more generally mathematical induction, you must be careful that the constants hidden by any asymptotic notation are the same constants throughout the proof.