知识卡片
矩阵链按区间长度填表
计算 m[i,j] 时需先得到所有更短左右子区间的成本,因此从长度 1 的对角线起,逐步填长度 2、3…n 的区间。
n 个矩阵共有 Θ(n²) 个区间状态,每态最多枚举 n−1 个分割,时间 O(n³)、表空间 Θ(n²);紧时间界留待习题证明。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第14章 动态规划 · 查看原书依据
the algorithm should fill in the table m from shorter matrix chains to longer matrix chains.
参考来源
- 位置:《算法导论(第4版)》第 14 章 14.2–14.3 节(`OEBPS/chapter014.xhtml`,文本字符 [35000, 45000);图 14.5)。
- 结论依据:MATRIX-CHAIN-ORDER 按链长递增填 m 与 s;区间数 Θ(n²)、每区间尝试至多 n−1 个分界,原文给 O(n³) 上界,紧界交习题证明。
- 原始内容:the algorithm should fill in the table m from shorter matrix chains to longer matrix chains.