首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知矩阵Am*n和Bn*p相乘的时间复杂度为O(mnp)。矩阵相乘满足结合律,如三个矩阵A、B、C相乘的顺序可以是(A*B)*C也可以是A*(B*C)。不同的相乘顺序所需进行的乘法次数可能有很大的差别。因此确定n个矩阵相乘的最优计算顺序是一个非常重要的问题
已知矩阵Am*n和Bn*p相乘的时间复杂度为O(mnp)。矩阵相乘满足结合律,如三个矩阵A、B、C相乘的顺序可以是(A*B)*C也可以是A*(B*C)。不同的相乘顺序所需进行的乘法次数可能有很大的差别。因此确定n个矩阵相乘的最优计算顺序是一个非常重要的问题
admin
2020-08-10
33
问题
已知矩阵Am*n和Bn*p相乘的时间复杂度为O(mnp)。矩阵相乘满足结合律,如三个矩阵A、B、C相乘的顺序可以是(A*B)*C也可以是A*(B*C)。不同的相乘顺序所需进行的乘法次数可能有很大的差别。因此确定n个矩阵相乘的最优计算顺序是一个非常重要的问题。已知确定n个矩阵A,A2......An相乘的计算顺序具有最优子结构,即A1A2......An的最优计算顺序包含其子问题A1A2......Ak和Ak+1Ak+2……An (l<=k
可以列出其递归式为:
其中,Ai的维度为pi-1*pi m[i,j]表示AiAi+1……Aj最优计算顺序的相乘次数。
先采用自底向上的方法求n个矩阵相乘的最优计算顺序。则求解该问题的算法设计策
略为(62)。算法的时间复杂度为(63),空间复杂度为(64)。
给定一个实例,(POPi……P5)=(20,15,4,10,20,25),最优计算顺序为(65)。
(62)
选项
A、分治法
B、动态规划法
C、贪心法
D、回溯法
答案
B
解析
转载请注明原文地址:https://kaotiyun.com/show/DUCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
根据以下关于学校构成的说明回答问题1至问题3。【说明】学校中有若干系,每个系有若干班级和教研室,每个教研室有若干教员,其中有的教授和副教授各带有若干研究生;每个班有若干学生,每个学生选修若干课程,每门课可由若干学生选修。【问题1
识别关联的多重度是面向对象建模过程中的一个重要步骤。请根据说明中给出的描述,将如图6-18所示中(1)~(6)空缺处的内容填写完整。该电子商务公司还对外开放一项出租图书和唱碟的业务。由于业务需求,该公司委托软件开发公司A开发一套信息管理系统。该系统将记
阅读下列说明,根据要求回答问题1~问题3。[说明]某企事业单位资料室需要建立一个图书管理系统,初步的需求分析结果如下:(1)资料室有图书管理员若干名,他们负责已购入图书的编目和借还工作,每名图书管理员的信息包括工号和姓名;(
阅读以下说明,回答问题1、问题2和问题3。【说明】某单位正在使用一套C/S模式的应用软件系统,现在需要升级为B/S应用模式,但需要保持业务的连续性。开发人员提出用WebService作为中间层的接口进行开发。【问题1】请
阅读下列说明和E-R图,回答问题1至问题3。[说明]有个关于运动会的管理系统,在该系统中,委员会为每一个参赛的运动员赋以一个唯一的编号“运动员号”,同时记录姓名、性别、年龄和队名,姓名和队名必须填写。一个运动员属于且只属于一个
阅读以下说明和C代码,将应填入(n)处的字句写在对应栏内。[说明]下面程序用来将打乱的单词还原为原来的次序,比如将rty还原为try。单词的原来次序存储于wordlist.txt文件中,原则上可用穷举法(rty对应的穷举为:rty、ry
阅读下列说明和Java代码,将应填入(n)处的字句写在答题纸的对应栏内。[说明]某大型商场内安装了多个简易的纸巾售卖机,自动出售2元钱一包的纸巾,且每次仅售出一包纸巾。纸巾售卖机的状态图如图6-1所示。采用状态(State)模式来实现
分析车辆的状态和事件,指出图2-1中的(1)、(2)、(3)、(4)分别是什么?指出UML中活动图的含义,并说明活动图和状态图的区别与联系。
若有一个仓库,可以存放P1和P2两种产品,但是每次只能存放一种产品。要求:①w=P1的数量-P2的数量②-i<w<k(i,k为正整数)若用PV操作实现P1和P2产品的入库过程,至少需要(1)个同步信号量及(2)个互斥信号量,其中,同步信号
某仓库有两名发货员,一名审核员。当顾客提货时,只要发货员空闲,允许顾客进入仓库提货,顾客离开时,审核员检验顾客提货是否正确。其工作流程如右下图所示。为了利用PV操作正确地协调他们之间的工作,设置了两个信号量S1和S2,且S1的初值为2, S2的初值为1。图
随机试题
工程量清单中有标价的单价或总额包括了工、料、机、管理、利润、缺陷修复、税金等费用,以及合同中明示或暗示的所有()。
绝大多数的政策变动都采取的方式是()
既抑制原核生物又抑制真核生物蛋白质生物合成的抗生素是
()决定了投资项目的实际规模。
负有安全生产监督管理职责部门的职权包括()。
养花专业户李某为防止偷花,在花房周围私拉电网。一日晚,白某偷花不慎触电,经送医院抢救,不治身亡。李某对这种结果的主观心理态度是什么?()
上述几个地区中,卫生机构总数最多的地区是()。
所有的金属都能导电,铜是金属,所以铜能导电。以下哪项与上文推理形式相同?
等价分类技术是【】设计方案的一种。
Theterm"jointinternationalbusinessventure",jointventureforshort,hascometomeanmanythingstomanypeople.Itsometi
最新回复
(
0
)