首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知矩阵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
28
问题
已知矩阵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)。
(64)
选项
A、O(n2)
B、O(n2lgn)
C、O(n3)
D、O(2n)
答案
A
解析
转载请注明原文地址:https://kaotiyun.com/show/PUCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读以下说明,将应填入(n)处的字句写在答卷纸的对应栏内。【说明】下面的程序为堆排序程序,其中函数adjust(i,n)是把以R[i](1≤i≤┕i/2┙)为根的二叉树调整成堆的函数,假定R[i]的左、右子树已经是堆,程序中的,是在主函数中说明
阅读以下说明和图,回答问题1至问题3,将解答写在对应栏内。【说明】某教学管理系统的用户是教学管理人员、教师和学生。系统主要提供学生选课管理和学生成绩管理两方面的功能。(1)学生选修课管理主要功能是管理新学期开始时,学生对选
该网上信用卡管理系统(CCMS)的顶层数据流图如图4-10所示。请根据系统功能描述和数据流图,并使用[说明]中的词汇,将图4-10中(1)~(4)空缺处的内容填写完整。除了表4-11和表4-12给出的用例之外,从以上[说明]陈述中还可以获取哪些由信用
图7-13是对该IC卡加油机应用系统的基本流路径和备选流路径的描述,请用试题描述中的相应字母(见表7-15和表7-16)将图中(1)~(6)空缺处的内容填写完整。假如加油机内油量足够,油价为5元/升,用户的账户金额为800元,那么在基本流A4输入油量
把上面用关系表示的实体,实体与实体之间的联系,用E-R图表示出来,要求在图中表示联系的类型(1:1,L:N,M:N)。用SQL语言写出查询:查询年龄不在20~23岁(包括20岁和23岁)之间的学生的姓名,系别和年龄。
阅读下列说明和c函数代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点,且每个结点仅访问一次的过程。函数InOrder。()借助栈实现二叉树的非递归中序遍历运算
根据问题描述,补充四个联系,完善图5—2的实体联系图。联系名可用联系l、联系2、联系3和联系4代替,联系的类型分为l:1、l:n和m:n。为了使商场有紧急事务时能联系到轮休的员工,要求每位员工必须且只能登记一位紧急联系人的姓名和联系电话,不同的员工
根据以上说明设计的E—R图如图6—3所示,请指出地址簿与用户、电子邮件账号与邮件、邮件与附件之间的联系类型。(1)请指出[问题2]中给出的地址簿、邮件和附件关系模式的主键,如果关系模式存在外键请指出。(2)附件属于弱实体吗?请用50字以内的文字说明
根据以上说明设计的E—R图如图6—3所示,请指出地址簿与用户、电子邮件账号与邮件、邮件与附件之间的联系类型。该邮件客户端系统的主要关系模式如下,请填补(a)~(c)的空缺部分。用户(用户名,用户密码)地址簿((a),联系人编号,
当在软件工程的环境中考虑风险时,主要基于Charette提出的3个概念。以下选项中不属于这3个概念的是(1)。项目风险关系项目计划的成败,(2)关系着软件的生存能力。在进行软件工程风险分析时,项目管理人员要进行4种风险评估活动,这4种活动分别是(3)以及确
随机试题
若P(A)=P(B)=P(C)=,P(AB)=P(BC)=0,P(AC)=,则A、B、C中至少有一个发生的概率为_____.
葡萄球菌可分为金黄色葡萄球菌、表皮葡萄球菌和腐生葡萄球菌3类,其分类依据主要是
治疗指数
下列各项目中,不属于存货的有()。
QDII产品投资金融衍生品应限于()。
C公司生产中使用甲零件,全年共需耗用3600件,该零件既可自行制造也可外购取得。如果自制,单位制造成本为10元,每次生产准备成本34.375元。每日生产量32件。如果外购。购入单价为9.8元,从发出订单到货物到达需要10天时间,一次订货成本72元。外购零件
下列关于税务行政处罚权的表述中,正确的是()。(2009年)
评价时以学生所在团体的平均成绩为参照标准,根据其在团体中的相对位置来报告评价结果的评价是()。
下列选项中三国典故与哲学论断对应错误的是:
IMF
最新回复
(
0
)