首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
两个矩阵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
41
问题
两个矩阵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
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明和C代码,将应填入(n)处的字句写在对应栏内。【说明】栈(Stack)结构是计算机语言实现中的一种重要数据结构。对于任意栈,进行插入和删除操作的一端称为栈顶(StockTop),而另一端称为栈底(StockBottom)。栈的基
下面是快速排序的伪代码,请填补其中的空缺;伪代码中的主要变量说明如下。A:待排序数组p,r:数组元素下标,从p到rq:划分的位置x:枢轴元素i:整型变量,用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴
若这三个事务允许并行执行,则请列举出有多少可能的正确结果。各个事务的内部结构如下所示。若事务不施加任何锁,则有多少可能的调度。T1:R1(GetAintot1;t1:=t1+1);U1(UpdateAfromt1);
通过该程序的算法用等价类设计测试用例,检查逻辑覆盖标准。用边界值分析法设计测试用例,检查逻辑覆盖标准。
(1)请说明流程图1中的文件F0、F1分别是哪个文件。(2)处理1和处理5分别按照哪些数据项进行分类?处理4能发现哪些错误(不需考虑设备故障错误)?
阅读以下说明,回答问题,将解答填入对应的解答栏内。[说明]给出一个接收三个数a、b、c作为三角形边长并输出三角形的类型的程序。程序代码如下所示:结点源代码行Areada,b,cB
根据题意,指出数据流图中缺失的数据流(a)的名称,并指出该数据流的起点。根据题意,补充数据字典中(d)、(e)、(f)处的空缺。
转换图中缺少哪三条数据流?请指明每条数据流的名称、起点和终点。在状态迁移图中,a,b,c分别表示什么事件?请用转换图中给出的事件名解答。
请认真阅读以下关于电子政务信息整合的叙述,根据要求回答问题1~问题4。[说明]公共服务、社会监督和宏观调控是我国政府的3个主要职能。实施电子政务建设,可以改善政府的公共服务质量,提高社会监管的效率和准确性,加强宏观经济调控的科学性。
工作流(Workflow)是针对业务流程中具有固定程序的常规活动而提出的一个概念,通过将业务流程分解,定义良好的任务、角色、规则和过程来进行执行和监控,达到提高生产组织水平和工作效率的目的。以下关于工作流叙述中,错误的是(1)。在UML中,用(2)
随机试题
青少年好发的肿瘤为()。
Farmersareallowedtogrowsmallgardensoftheirownandtheyselltheirvegetables______theblackmarket.
如果取精液检查,应在检查前至少几天内不排精。
华支睾吸虫对人的危害主要是
关于胰岛素治疗,下列不妥的是下列哪一部位不可注射胰岛素
治疗成人呼吸窘迫综合征最有效的措施为()
《中华人民共和国广告法》规定,药品、医疗器械广告不得有的内容是()
设齐次线性方程组当方程组有非零解时,k值为:
某工业企业仅生产甲产品,采用品种法计算产品成本。3月初在产品直接材料成本130万元,直接人工成本18万元,制造费用10万元。3月份发生直接材料成本80万元,直接人工成本4871元,制造费用6万元。3月末甲产品完工100件,在产品200件。月末计算完工产品成
Translatingisacomplexandfascinatingtask.Infact,A.Richardshasclaimedthatitisprobablythemostcomplextypeofeve
最新回复
(
0
)