知识卡片
记忆化以空间换时间
记忆化在首次求出子问题答案后缓存,以后按状态查表而不重算。它增加存储和查找开销,却可在独立子问题数及每个状态求解成本均为多项式时把重复递归降到多项式时间;不应只凭“用了缓存”断言一定高效。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第14章 动态规划 · 查看原书依据
Saving subproblem solutions comes with a cost: the additional memory needed to store solutions.
参考来源
- 位置:《算法导论(第4版)》第 14 章 14.1 节(`OEBPS/chapter014.xhtml`,文本字符 [10000, 15000))。
- 结论依据:14.1 节规定首次求子题后保存答案、再次访问查表;增加内存可免重算。原文将多项式时间条件限定为状态种类数与每态求解成本都为多项式。
- 原始内容:Saving subproblem solutions comes with a cost: the additional memory needed to store solutions.