首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知矩阵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
52
问题
已知矩阵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
软件设计师上午基础知识考试
软考中级
相关试题推荐
【说明】设有下列关于图书借阅系统的E—R图。图中矩形表示实体,圆表示属性,双圆表示关键字属性,菱形表示实体间的联系。假定已通过下列SQL语言建立了基本表:CREATETABLEReaders(RaoCHAR(
阅读下列Java程序和程序说明,将应填入(n)处的字句写在对应栏内。【说明】清点盒子。本程序当用户输入一个整数值时,一切正常;当输入其他数值时,程序就出错。现在已做了改进,请填空。importjava.text.NumberFormat;
下面是一个Applet程序,其功能是在绘图区域中通过鼠标的移动来绘制直线,并且有清除绘图区域按钮,用来清除已经绘制的图像。程序运行结果如图5所示。importjava.awt.*;importjava.applet.*;
企业信息整合、共享需要一个代表企业身份的信息,该信息应该具有唯一性和易管理性,上述表格中信息项(1)代表企业身份最合适。该市政府各委、办、局已经分别投资立项建设了业务自动化系统和信息管理系统,仅从保护投资的角度出发,也难以一下子按企业基础数据集
阅读以下某前台销售子系统的技术说明和UML图,根据要求回答问题1~问题4。[说明]某超市管理系统的前台销售子系统以最基本的方式处理销售业务。系统的功能需求如下:①记录每种商品的编号、单价和现有数量;②为顾客选购的商品计价、收
阅读下列说明和数据流图,回答问题1至问题3。[说明]图书管理系统旨在用计算机对图书进行管理,包括图书的购入、借阅、归还以及注销。管理人员可以查询某位读者、某种图书的借阅情况,还可以对当前图书借阅情况进行一些统计,给出统计表格,以便掌握图
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】对有向图进行拓扑排序的方法是:(1)初始时拓扑序列为空;(2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某网上药店允许顾客凭借医生开具的处方,通过网络在该药店购买处方上的药品。该网上药店的基本功能描述如下:(1)注册。顾客在买药之前,必须先在网上药店注册。注册过程中需填写顾客资料
(2012年上半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系,对某些作业,在
ARP协议的作用是(61),ARP报文封装在(62)中传送。
随机试题
ReadcarefullythefollowingexcerptonChina’sdemandingstricterrulesforlivestreaming,andthenwriteyourresponseinNO
在成人呼吸窘迫综合征(ARDS)的生机制中,下列哪种细胞起了最要的作用
A.大剂量催产素B.孕激素C.小剂量催产素D.生乳素E.以上都不是
以汇票、本票、支票、债权、存款单、仓单、提单出质的,出质人和债权人应当订立质押合同的,质押合同自()起生效。
根据《B艮单信用证统一惯例》,银行在以下哪种情况下可拒绝付款?
不属于有关溢油动力学过程的漂移过程运动速度组成的是()。
属于工程成本分析方法中基本分析方法的有()。
商业银行代销代理其他机构发行的产品投资于非标准化债权资产或股权性资产的,需由商业银行所在省或自治区省级分行审核批准。()
提出“有教无类”教育思想的古代教育家是()。
WhichofthefollowingstatementsaboutFlowersandYeoistrue?WhichofthefollowingisNOTmentionedasacauseoftheprob
最新回复
(
0
)