首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知矩阵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
99
问题
已知矩阵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)。
(65)
选项
A、(((A1*A2)*A3)*A4)*A5
B、A1*(A2*(A3*(A4*A5)))
C、((A1*A2)*A3)* (A4*A5)
D、(A1*A2) *( (A3*A4)*A5)
答案
D
解析
转载请注明原文地址:https://kaotiyun.com/show/WUCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读以下说明,回答问题1~2,将解答填入对应的解答栏内。[说明]设某商业集团数据库中三个实体集。一是“仓库”实体集,属性有仓库号、仓库名和地址等;二是“商店”实体集,属性有商店号、商店名、地址等;三是“商品”实体集,属性有商品号、商品名、单价。
阅读下列说明和数据流图,回答问题1-问题3。【说明】某医院收费系统的主要功能是收取病人门诊的各项费用。系统的收费功能分为3个方面:病历收费、挂号收费和根据处方单内容收取检查或药物费用。1.病
阅读下列Java程序和程序说明,将应填入(n)处的字句写在对应栏内。【说明】下面的程序先构造Point类,再顺序构造Ball类。由于在类Ball中不能直接存取类Point中的xCoordinate及yCoordinate属性值,Ball中的toSt
阅读以下说明和C语言函数,将应填入(n)处的字句写在答题纸的对应栏内。【说明】一棵非空二叉树中“最左下”结点定义为:若树根的左子树为空,则树根为“最左下”结点;否则,从树根的左子树根出发,沿结点的左孩子分支向下查找,直到某个结点不存在左孩
根据说明中的描述,使用表3-11给出的用例名称,给出图3-22中U1、U2和U3所对应的用例。简要解释图3-22中用例U1和U3之间的extend关系的内涵。
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】对有向图进行拓扑排序的方法是:(1)初始时拓扑序列为空;(2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该
阅读下列说明和图,回答问题l至问题3,将解答填入答题纸对应栏内。【说明】某城市拟开发一个基于web的城市黄页,公开发布该城市重要的组织或机构(以F统称为客户)的基本信息,方便城市生活。该系统的主要功能描述如下:(1)搜索信息:任何使用Internet的
下列叙述中正确的是(52)。
下面关于校验方法的叙述,(5)是正确的。
软件开发的螺旋模型综合了瀑布模型和演化模型的优点,还增加了(20)。采用螺旋模型时,软件开发沿着螺线自内向外旋转,每转一圈都要对(21)进行识别和分析,并采取相应的对策。螺旋线第一圈的开始点可能是一个(22)。从第二圈开始,一个新产品开发项目开始了,新产品
随机试题
设x1=1,x2=2均为y=alnx+bx2+3x的极值点,求a,b.
肺下界的体表投影在腋中线相交于()
甲状腺功能亢进症的主要临床表现是
癫痫强直一阵挛发作时最主要的护理是
饥不欲食可见于()
胡锦涛同志在十八大报告中指出,要全面落实经济建设、政治建设、文化建设、社会建设()五位一体总体布局。
要做到遵纪守法,对每个干部职工来说,必须做到()。
2008年到2012年间,该市文化产业总值增长最快的年份是()。
数据管理技术的发展是与计算机技术及其应用的发展联系在一起的,经历了由低级到高级的发展过程。分布式数据库、面向对象数据库等新型数据库是属于()发展阶段的。
TeamWorkTheclassteacher/sandstudent/sneedtoworklikeateam,withtheteacherbeingthecoachwhoneedstocontin
最新回复
(
0
)