知识卡片

普通读书笔记卡 · 3623.c.2.a

状态表大小与依赖数分开估

理解等级:高级

章末给动态规划分类:表规模 O(n^t),每个状态依赖 O(n^e) 个其他状态,分别记作 tD/eD。它提醒估计总成本时既看状态数,也看每态转移范围;该记号是文献分类,不是任何动态规划都自动达到的时间公式。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

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