不同计算顺序的数量 ■设n个矩阵的连乘积有P(n)个不同的计算顺序 伽ξ筧Pm卿方槌将原矩阵序列 分成两个矩阵子序列,k=1,…m:1再分别 对两个联列完线掉 后对结果加括 号,便得到原序葪的完坠册括号方式 ■解此递归方程可得P(n)=C(n-1),其中 C(n)=n+ 2n1=92(4hn n ■所以P(n)随n的增长呈指数增长。因而穷举搜 索法不是有效的算法。 算法设计与分析算法设计与分析 4 不同计算顺序的数量 ◼ 设n个矩阵的连乘积有P(n)个不同的计算顺序。 ◼ 先在第k个和第k+1个矩阵之间将原矩阵序列 分成两个矩阵子序列，k=1，…，n；再分别 对两个子序列完全加括号，最后对结果加括 号，便得到原序列的一种完全加括号方式。 ◼ 由此可得出关于P(n)的递归式： P(n) = 1 n = 1 n–1 ∑P(k) P(n–k) n＞1 k=1 ◼ 解此递归方程可得P(n) = C(n–1)，其中 C(n) = 1 n+1 2n n = Ω(4n /n3/2) ◼ 所以P(n)随n的增长呈指数增长。因而穷举搜 索法不是有效的算法