知识卡片

普通读书笔记卡 · 3623.b.1.a.1

记忆化以空间换时间

理解等级:高级

记忆化在首次求出子问题答案后缓存,以后按状态查表而不重算。它增加存储和查找开销,却可在独立子问题数及每个状态求解成本均为多项式时把重复递归降到多项式时间;不应只凭“用了缓存”断言一定高效。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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.