首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
两个矩阵Am*n和Bn*n相乘,用基本的方法进行,则需要的乘法次数为m*n*p。多个矩阵相乘满足结合律,不同的乘法顺序所需要的乘法次数不同。考虑采用动态规划方法确定Mi,M(i+1),…,Mj多个矩阵连乘的最优顺序,即所需要的乘法次数最少。最少乘法次数用m
两个矩阵Am*n和Bn*n相乘,用基本的方法进行,则需要的乘法次数为m*n*p。多个矩阵相乘满足结合律,不同的乘法顺序所需要的乘法次数不同。考虑采用动态规划方法确定Mi,M(i+1),…,Mj多个矩阵连乘的最优顺序,即所需要的乘法次数最少。最少乘法次数用m
admin
2019-07-12
38
问题
两个矩阵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
1
、M
2
、M
3
、M
4
相乘的维度序列为2、6、3、10、3,采用上述算法求解,则乘法次数为(2)。
(2)
选项
A、1 56
B、144
C、1 80
D、360
答案
B
解析
本题考查算法设计与分析的基础知识。
矩阵链乘是一个最优化问题,求解n个矩阵相乘的最优加括号方式,可以用动态规划方法来求解。题干已经给出动态规划求解的递归式。根据上式计算m的值,同时记录k的佰到s中。
可以得到最优的加括号方式((M
1
M
2
)(M
3
M
4
)),乘法次数为144。因此(65)题选择B。
而根据该递归式自底向上求解时,应该用三重循环进行,即矩阵链长度1从1到n,子矩阵链起始位置,即i从1到n-1+1,矩阵链分开的位置k,从i到i-1。因此时间复杂度为O(n
3
)。
转载请注明原文地址:https://kaotiyun.com/show/kQCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
图(a)中只有一个外部实体E1。使用【说明】中的词语,给出E1的名称。在进行系统分析与设计时,面向数据结构的设计方法(如Jackson方法)也被广泛应用。简要说明面向数据结构设计方法的基本思想及其适用场合。
通过该程序的算法用等价类设计测试用例,检查逻辑覆盖标准。用边界值分析法设计测试用例,检查逻辑覆盖标准。
阅读下列程序和控制流图,将应填入(n)的字句。【程序】下面是一段求最大值的程序,其中datalist是数据表,n是datalist的长度。intGetMax(intn,intdatalist[]){intk=0;
在需求分析阶段,采用UML的用例图描述系统功能需求,如图1-6所示。指出图1-6中(1)(2)、(3)、(4)分别是哪个用例?图1-7采用协作图描述借书和还书两个动态过程的交互关系。在UML中,重复度(multiplicity)定义了某个实体的一个实例
根据E-R图中给出的词汇,按照“有关模式名(属性1,属性2,…)”的格式,将此E-R图转换为关系模式,并指出每个关系模式中的主码和外码,其中模式名根据需要取实体名或联系名。要求其中的关系模式至少属于第三范式。如下的SQL语言用于查询“在该银行中一笔贷款
【说明】设有关于银行借贷管理系统的E-R图。图中矩形表示实体,圆表示属性,双圆表示关键字属性,菱形表示实体间的联系。为了答题的方便,图中的实体和属性同时给出了中英文说明,回答问题时只需写出英文名即可。
阅读以下说明和c++码,将应填入(n)处的字名写在对应栏内。[说明]从键盘输入一个字符ch,输出该字符在文本文件input.txt的每一行中出现的次数。(必须调用函数鳋统计ch的出现次数,函数ff(str,ch)的功能是统计并返回字符ch在字符串
在UML中,用例代表一个完整的功能,如与角色通信、进行计算或在系统内工作等。请简要说明用例具有哪些的特征,并指出用例图中(1)~(3)处表示的内容。协作图与时序图是同构的,二者表示的都是同样的系统交互活动,只是各自的侧重点不同而已。根据题目提供的信息,
随机试题
总体规划是国民经济和社会发展的()的规划。
酸碱质子理论认为,H2O既是一种酸,又是一种碱。()
预防维生素D缺乏最重要的方法是
A.个体行为干预B.群体行为干预C.行为指导处方D.健康促进行为E.心理防御机制专题讲座属于
粒系细胞的免疫标志是
患者男性,35岁,因惊恐障碍长期口服阿米替林,175mg,1次/日。因家中变故,惊恐发作加重,每周发作4~5次,前来就诊。诊断:焦虑症。医嘱:治疗用药的用药方法:地西泮10mg,2次/日;帕罗西汀20mg,口服,1次/日;阿米替林150nlg,
关于现浇混凝土工程模板支撑系统立柱对接接头的说法,正确的是()。
学生心理发展的基本特征包括()
下面是8086/8088微处理器有关操作的描述: ①计算有效地址 ②分析指令,产生控制信号 ③计算物理地址,传送执行过程中需要的操作数或运行结果 ④预取指令至指令队列缓冲器 其中由总线接口部件BIU完成的操作是(
ReadthefollowingpassagecarefullyandthenwriteasummaryofitinEnglishinabout150words.Manyoftoday’syoungpeo
最新回复
(
0
)