两个矩阵Am*n和Bn*n相乘,用基本的方法进行,则需要的乘法次数为m*n*p。多个矩阵相乘满足结合律,不同的乘法顺序所需要的乘法次数不同。考虑采用动态规划方法确定Mi,M(i+1),…,Mj多个矩阵连乘的最优顺序,即所需要的乘法次数最少。最少乘法次数用m

admin2019-07-12  23

问题 两个矩阵Am*n和Bn*n相乘,用基本的方法进行,则需要的乘法次数为m*n*p。多个矩阵相乘满足结合律,不同的乘法顺序所需要的乘法次数不同。考虑采用动态规划方法确定Mi,M(i+1),…,Mj多个矩阵连乘的最优顺序,即所需要的乘法次数最少。最少乘法次数用m[i,j]表示,其递归式定义为:

其中,i、j和k为矩阵下标,矩阵序列中Mi的维度为(pi-1)*pi。采用自底向上的方法实现该算法来确定n个矩阵相乘的顺序,其时间复杂度为(1)。若四个矩阵M1、M2、M3、M4相乘的维度序列为2、6、3、10、3,采用上述算法求解,则乘法次数为(2)。
(2)

选项 A、1 56
B、144
C、1 80
D、360

答案B

解析 本题考查算法设计与分析的基础知识。
矩阵链乘是一个最优化问题,求解n个矩阵相乘的最优加括号方式,可以用动态规划方法来求解。题干已经给出动态规划求解的递归式。根据上式计算m的值,同时记录k的佰到s中。

可以得到最优的加括号方式((M1M2)(M3M4)),乘法次数为144。因此(65)题选择B。
而根据该递归式自底向上求解时,应该用三重循环进行,即矩阵链长度1从1到n,子矩阵链起始位置,即i从1到n-1+1,矩阵链分开的位置k,从i到i-1。因此时间复杂度为O(n3)。
转载请注明原文地址:https://jikaoti.com/ti/d6G7FFFM
0

相关试题推荐
最新回复(0)