知识卡片

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

矩阵链按区间长度填表

理解等级:中级

计算 m[i,j] 时需先得到所有更短左右子区间的成本,因此从长度 1 的对角线起,逐步填长度 2、3…n 的区间。

n 个矩阵共有 Θ(n²) 个区间状态,每态最多枚举 n−1 个分割,时间 O(n³)、表空间 Θ(n²);紧时间界留待习题证明。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

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