答案及解析：[填空题]两个矩阵Am*n和Bn*p相乘，用基本的方法进行，则需要的乘法次数为m*n*p。多个矩阵相乘满足结合律，不同的乘法顺序所需要的乘法次数不同。考虑采用动态规划方法确定Mi，M（i+1），…，Mj多个矩阵

问题：

[填空题] 两个矩阵Am*n和Bn*p相乘，用基本的方法进行，则需要的乘法次数为m*n*p。多个矩阵相乘满足结合律，不同的乘法顺序所需要的乘法次数不同。考虑采用动态规划方法确定Mi，M（i+1），…，Mj多个矩阵连乘的最优顺序，即所需要的乘法次数最少。最少乘法次数用m[i,j]表示，其递归式定义为：
中级软件设计师,历年真题,2016年下半年（上午）《软件设计师》真题

其中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.156
B.144
C.180
D.360

Tags：软件水平考试中级软件设计师试题及答案

答案解析：

╋纠错

您可能感兴趣的问题