知识卡片
归纳基例须覆盖终止区间
递归式的代入证明不能只算归纳步。若递归子问题可能落入若干常数规模,需选一个能覆盖全部终止情况的基例区间,再调大前导常数使猜测在该区间成立。
如此才能把局部不等式扩展到全部允许的 n。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第4章 分治策略 · 查看原书依据
We’ve shown that the inductive hypothesis holds for the inductive case, but we also need to prove that the inductive hypothesis holds for the base cases of the induction
参考来源
- 位置:《算法导论(第4版)》第 4 章 4.3–4.4 节(`OEBPS/chapter004.xhtml`,文本字符 [30000, 35000))。
- 结论依据:4.3 节在 T(n)≤cn lg n 的归纳步后,另验 n₀≤n<2n₀ 的全部基例,并通过选择 n₀ 与 c 使不等式成立。
- 原始内容:We’ve shown that the inductive hypothesis holds for the inductive case, but we also need to prove that the inductive hypothesis holds for the base cases of the induction