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

admin2019-07-12 49

问题两个矩阵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)

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

软考中级

阅读以下说明和c++码，将应填入(n)处的字名写在的对应栏内。[说明]以下函数完成求表达式的值，请填空使之完成此功能。floatsum(floatx){floats=0.0;ints

该程序的控制流图中A～E分别是什么?用基本路径覆盖法给出测试路径。

设计一的关系模式Invoice最高满足第几范式?为什么?设计一和设计二哪个更加合理?为什么?设计二中关系Merchandise中由属性price表示商品价格，关系Invoice,detail中的属性unitprice也表示商品价格。两个是否有必要同

根据这张通知书所提供的信息，设计了一个E-R模型，如图12-6所示。请将(n)处补充完整。将问题1中的E-R模型(图12-6)转换成4个关系数据模型，要求标注主码和外码。

试分析该关系模式中的函数依赖，并指出关系模式的候地选码。如下的SQL语句是检索“信息系(IS)和计算机科学系(CS)的学生的姓名和性别”的不完整语句，请在空缺处填入正确的内容。SELECT(1)FROM(2)WHERE(3)

阅读以下说明和JAVA2代码，填入(n)处的。[说明]以下JAVA程序实现了在接口interfaceiShape2D的定义和应用，仔细阅读代码和相关注释，将程序补充完整。[代码6-1]interfaceiShape2D

Word文档中，创建表格的方式不正确的是()。

当申报的成交价格明显低于正常的市场价时，应以()作为缴纳税费的依据。

现配制试配强度为42.23MPa的混凝土，选用水泥的实际强度为52MPa，粗骨料为5～40mm粒径的碎石，回归系数αa＝0.46，αb＝0.06，则所需水灰比为()。

企业的日常薪酬管理包括()。

1

用于去掉一个字符串的右边的空白部分的函数是______。

Hamilah,theDoctorscookwasinawhirl(混乱，繁忙)ofgreatactivity.Shewascontinuallystickingherhead【C1】______ofthecookhou

Whatdeterminesthekindofpersonyouare?Whatfactorsmakeyoumoreorlessbold,intelligent,orabletoreadamap?Allof