知识卡片
矩阵链穷举括号数指数增长
完整括号化把 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.