- 当前位置:
- 首页
- 试题
- 软件设计师
- 2017年11月17日软件设计师每日一练
两个矩阵A
m*n和B
n*p相乘,用基本的方法进行,则需要的乘法次数为m*n*p。多个矩阵相乘满足结合律,不同的乘法顺序所需要的乘法次数不同。考虑采用动态规划方法确定M
i,M
(i+1),…,M
j多个矩阵连乘的最优顺序,即所需要的乘法次数最少。最少乘法次数用m[i,j]表示,其递归式定义为:
其中i、j和k为矩阵下标,矩阵序列中M
i的维度为(p
i-1)*p
i采用自底向上的方法实现该算法来确定n个矩阵相乘的顺序,其时间复杂度为( )。若四个矩阵M
1、 M
2、M
3、M
4相乘的维度序列为2、6、3、10、3,采用上述算法求解,则乘法次数为( )。