首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
两个矩阵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
40
问题
两个矩阵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
软件设计师上午基础知识考试
软考中级
相关试题推荐
根据[说明]中的描述,使用参与者列表的英文名称,给出ORS用例图中A1~A4所对应的参与者。根据[说明]中的描述,给出ORS用例图中(1)和(2)所对应的关系。
使用说明中的词语,给出上述顶层数据流图中的外部实体E1~E4的名称。使用说明中的词语,给出上述0层数据流图中的数据存储D1~D3的名称。
该程序的控制流图中A~E分别是什么?为各测试路径设计测试用例。
阅读下列程序说明和C程序,将应填入(n)处的字句写在答卷纸的对应栏内。【程序说明】该程序定义了两个子函数strsort和strmerge。它们分别实现了将一个字符串按字母顺序排序和将两个字符串合并排序,并删去相同字符。在主函数里,先输入两个
阅读下列程序和控制流图,将应填入(n)的字句写在答题纸的对应栏内。【程序】下面是一段求最大值的程序,其中datalist是数据表,n是datalist的长度+intGetMax(intn,intdatalist[])
阅读以下说明,回答问题1至问题3,将答案写在对应栏内。【说明】在一个航空公司的航班管理系统中,有以下一些事实。(1)一个航班可能是一个或多个乘客的运输工具,每个乘客可能是一个或多个航班的旅客。(2)一个且仅一个飞行员必须对
设计一的关系模式Invoice最高满足第几范式?为什么?设计一和设计二哪个更加合理?为什么?设计二中关系Merchandise中由属性price表示商品价格,关系Invoice,detail中的属性unitprice也表示商品价格。两个是否有必要同
数据流图12-2缺少了两条数据流,请采用说明中的词汇给出此数据流名称,并指出方向。请补齐下列数据字典条目:系统命令=__________输入信息=__________个人资料=__________档案维护=_______
指出算法的流程图中(1)~(3)处的内容。指出测试用例设计中(4)~(9)处的内容。
阅读下列函数说明和C代码,应填入(n)处。[说明]假设设A和B均为顺序表,A’和B’分别为A和B中除去最大共同前缀后的子表(例如,A=(x,y,y,z,x,z),B=(x,y,y,z,y,x,x,z),则两者中最大的共同前缀为(x,y,y
随机试题
项目风险对策不包括()。
简述社会救助对象的范围。
采取分泌物做口腔真菌培养时,采集部位宜在
胰腺癌常好发于
极限的值是:
左边图形折起来,将得到右边的图形是()。
国家主席习近平在北京主持召开文艺工作座谈会并发表重要讲话。他强调,文艺是时代前进的号角,最能代表一个时代的风貌,最能引领一个时代的风气。他指出,一部好的作品,应该是把()放在首位。
依次填入下列各句横线处的词语,最恰当的一组是:( )。①这个句子所运用的比喻______三层意思,需要深入挖掘,才能真正体会到其中的妙处。②从这故事里可以看出,李贺从青少年时代起,就把全部心血______到诗歌创作上去了。
Accordingtothespeaker,howshouldmostofthenotesbetaken?
A、Heavyrainshaven’tstrokeQueenslandforalongtime.B、PeopleinQueenslandhavedonesomepreparationforit.C、Therewasn
最新回复
(
0
)