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

admin2019-07-12 47

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

其中，i、j和k为矩阵下标，矩阵序列中M_i的维度为(p_i-1)*p_i。采用自底向上的方法实现该算法来确定n个矩阵相乘的顺序，其时间复杂度为(1)。若四个矩阵M₁、M₂、M₃、M₄相乘的维度序列为2、6、3、10、3，采用上述算法求解，则乘法次数为(2)。
(2)

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

答案B

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

可以得到最优的加括号方式((M₁M₂)(M₃M₄))，乘法次数为144。因此(65)题选择B。
而根据该递归式自底向上求解时，应该用三重循环进行，即矩阵链长度1从1到n，子矩阵链起始位置，即i从1到n-1+1，矩阵链分开的位置k，从i到i-1。因此时间复杂度为O(n³)。

转载请注明原文地址:https://kaotiyun.com/show/kQCZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

软件设计师上午基础知识考试

软考中级

该程序的控制流图中A～E分别是什么?计算控制流图的McCabe环路复杂性。

上表中带下划线的为主码。请为还没有确定主码或是主码不合理的数据表选定最合适的主码。上面的关系模式中还有不是第二范式的，请将其转为第二范式。并确定新数据表的主码。

阅读以下说明，回答问题，将解答填入对应的解答栏内。[说明]给出一个接收三个数a、b、c作为三角形边长并输出三角形的类型的程序。程序代码如下所示：结点源代码行Areada,b,cB

阅读下列说明和图，回答问题1至问题3。【说明】某汽车数字仪表板将完成下述功能：(1)通过模/数转换，实现传感器和微处理器的接口。(2)在发光二极管面板上显示数据。(3)指示速度(mph)、行驶里程、油耗(mpg)等。(4)指

阅读以下关于某订单管理系统的技术说明、部分UML类图及C++代码，将C++程序中(1)～(5)空缺处的语句填写完整。[说明]某订单管理系统的部分UML类图如图5-15所示。图5-15中，Product表示产品，Produc

改革开放是在新的时代条件下带领人民进行的新的伟大革命，其目的是()

冬虫夏草的功效是

下列关于无菌包的使用方法的表述，正确的是()。

根据企业国有资产法律制度的规定，下列各项中，履行金融企业国有资产监督管理职责的是()。

事业单位人员聘用合同中的约定条款，只要不违反法律、法规、规章和政策的规定，则与必备条款具有同等效力，聘用合同缺乏约定条款不影响其效力。（）

【2011中央财经大学判断题第9题】依据利率平价理论，利率高的货币远期汇率是开水，利率低的货币远期汇率是贴水。()

设f(x)在[0，1]上连续，在(0，1)内可导，且f(0)=1，f(1)=0，则在(0，1)内至少存在一点ξ，使()

设有向图G有n个顶点，它的邻接矩阵为A，G中第i个顶点Vi的度为()。