首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
两个矩阵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
18
问题
两个矩阵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:待排序数组p,r:数组元素下标,从p到rq:划分的位置x:枢轴元素i:整型变量,用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴
根据[说明]中的描述,使用参与者列表的英文名称,给出ORS用例图中A1~A4所对应的参与者。根据[说明]中的描述,给出ORS用例图中(1)和(2)所对应的关系。
阅读下列程序说明,将应填入(n)处的字句写在答卷纸的对应栏内。【程序说明】对于一个公司的雇员来说,无非有3种:普通雇员、管理人员和主管。这些雇员有共同的数据:名字、每小时的工资,也有一些共同的操作:数据成员初始化、读雇员的数据成员及计算雇员
【说明】某超市的销售业务由一个销售业务管理系统进行管理,该系统每完成一次交易都需要提供顾客发票,其格式如表1-1所示。对于这样一个销售业务管理系统,分别给出了以下两种关系数据库的设计(下划线表示主关键字)设计一:顾客
阅读下列函数说明和C代码及流程图,将应填入(n)处的字句写在对应栏内[说明]分糖果问题是一个经典问题。问题描述如下:幼儿国有n(<20)个孩子围成一圈分糖果,老师先随机地发给每个孩子若干颗糖果,然后按以下规则调整:每个孩子同时将自己手中的糖果分
根据这张通知书所提供的信息,设计了一个E-R模型,如图12-6所示。请将(n)处补充完整。将问题1中的E-R模型(图12-6)转换成4个关系数据模型,要求标注主码和外码。
数据流图12-2缺少了两条数据流,请采用说明中的词汇给出此数据流名称,并指出方向。请补齐下列数据字典条目:系统命令=__________输入信息=__________个人资料=__________档案维护=_______
指出哪张图的哪些文件可以不必画出。根据系统功能和数据流图填充下列数据字典条目中的(1)和(2):试题得分表=准考证号+{课程名+成绩}考生名册=报名号+准考证号+姓名+通信地址+出生年份+文化程度+职业考生通知单=(1)
求供应红色零件北京供应商的编号、名称和状态。求零件颜色不是白色和黑色的供应商状态为1的订单的数量。
工作流(Workflow)是针对业务流程中具有固定程序的常规活动而提出的一个概念,通过将业务流程分解,定义良好的任务、角色、规则和过程来进行执行和监控,达到提高生产组织水平和工作效率的目的。以下关于工作流叙述中,错误的是(1)。在UML中,用(2)
随机试题
下列选项中,不属于社会规范的是()
乔木树种的生活型为()
试述伸直型肱骨髁上骨折的临床表现和诊断。
下列各项中,应计入营业税金及附加的有()。
某上市公司拟申请公开发行公司债券。该公司最近一期期末净资产额为2亿元人民币,3年前该公司曾发行5年期债券3000万元。该公司此次发行债券额最多不得超过()万元。
远洋公司为一综合性的生产企业,属于增值税一般纳税人。2019年6月发生下列事项:(1)当月销售货物按分期收款合同应取得含税销售款60000元,月底对方仍未支付。(2)2019年3月销售货物不含税金额30000元,发货的同时开具了增值税专用发票,本月初
义的学习指人和动物在生活过程中,凭借经验而产生的行为或行为潜能的相对()。
2.5岁患儿,自幼青紫,有蹲踞现象,胸片示肺血少。最可能的诊断为()。
釉质牙本质界是()。
A、763million.B、643million.C、553million.D、663million.A
最新回复
(
0
)