28-快速计算-矩阵连乘

选择背景色：黄橙洋红淡粉水蓝草绿白色选择字体：宋体黑体微软雅黑楷体选择字体大小：小中大特恢复默认

给定n个矩阵{A₁，A ₂，A₃，…，A _n}，其中，A _i 和A _i₊₁（i=1，2，…，n−1）是可乘的。矩阵乘法如图4-40所示。用加括号的方法表示矩阵连乘的次序，不同的计算次序计算量（乘法次数）是不同的，找出一种加括号的方法，使得矩阵连乘的计算量最小。

图4-40　矩阵乘法

例如：

A₁是M_5×10的矩阵；

A₂是M_10×100的矩阵；

A₃是M_100×2的矩阵。

那么有两种加括号的方法：

（1）（A₁ A₂）A₃；

（2）A₁（A₂ A₃）。

第1种加括号方法运算量：5×10×100+5×100×2=6000。

第2种加括号方法运算量：10×100×2+5×10×2=2100。

可以看出，不同的加括号办法，矩阵乘法的运算次数可能有巨大的差别！