知识卡片
状态表大小与依赖数分开估
章末给动态规划分类:表规模 O(n^t),每个状态依赖 O(n^e) 个其他状态,分别记作 tD/eD。它提醒估计总成本时既看状态数,也看每态转移范围;该记号是文献分类,不是任何动态规划都自动达到的时间公式。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第14章 动态规划 · 查看原书依据
They call a dynamic-programming algorithm tD/eD if its table size is O(nt) and each entry depends on O(ne) other entries.
参考来源
- 位置:《算法导论(第4版)》第 14 章问题与章末注释(`OEBPS/chapter014.xhtml`,文本字符 [115000, 120000))。
- 结论依据:章注引用 Galil 与 Park 的 tD/eD 分类:表大小 O(n^t)、每项依赖 O(n^e) 项;这是算法分类参数,不直接证明总时间。
- 原始内容:They call a dynamic-programming algorithm tD / eD if its table size is O ( n t ) and each entry depends on O ( n e ) other entries.