两个矩阵Am*n和Bn*p相乘,用基本的方法进行,则需要的乘法次数为m*n*p。

免费题库2022-08-02  63

问题 两个矩阵Am*n和Bn*p相乘,用基本的方法进行,则需要的乘法次数为m*n*p。多个矩阵相乘满足结合律,不同的乘法顺序所需要的乘法次数不同。考虑采用动态规划方法确定Mi,M(i+1),…,Mj多个矩阵连乘的最优顺序,即所需要的乘法次数最少。最少乘法次数用m[i,j]表示,其递归式定义为:其中i、j和k为矩阵下标,矩阵序列中Mi的维度为(pi-1)*pi采用自底向上的方法实现该算法来确定n个矩阵相乘的顺序,其时间复杂度为(  )。若四个矩阵M1、M2、M3、M4相乘的维度序列为2、6、3、10、3,采用上述算法求解,则乘法次数为(  )。问题1选项A.O(n2)B.O(n2lgn)C.O(n3)D.O(n3lgn)问题2选项A.156B.144C.180D.360

选项

答案 CB

解析 四个矩阵分别为:
2*66*33*1010*3
先计算:M1*M2及M3*M4,计算次数分别为:
2*6*3=36,3*10*3=90。
然后结果相乘,计算次数为:
2*3*3=18。
36+90+18=144。
转载请注明原文地址:https://tihaiku.com/congyezige/2409669.html

最新回复(0)