知识卡片

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

矩阵链穷举括号数指数增长

理解等级:中级

完整括号化把 n 个矩阵递归拆成左右两个子链,分界有 n−1 种,因而所有括号化方案数随 n 指数增长。即使每种方案的代价易算,逐一穷举也不是有效的求最优顺序方法。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第14章 动态规划 · 查看原书依据

      The number of solutions is thus exponential in n, and the brute-force method of exhaustive search makes for a poor strategy when determining how to optimally parenthesize a matrix chain.

    参考来源

    - 位置:《算法导论(第4版)》第 14 章 14.2–14.3 节(`OEBPS/chapter014.xhtml`,文本字符 [25000, 30000);Art_P456–P457)。 - 结论依据:14.2 节按最后一次乘法的分界枚举 n−1 类括号化;原文指出方案数指数增长,Ω(2^n) 界是练习14.2-3要求证明的结论。 - 原始内容:The number of solutions is thus exponential in n , and the brute-force method of exhaustive search makes for a poor strategy when determining how to optimally parenthesize a matrix chain.