首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知矩阵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
47
问题
已知矩阵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
软件设计师上午基础知识考试
软考中级
相关试题推荐
求供应红色零件北京供应商的编号、名称和状态。将所有北京供应商的状态为2的修改为1。
阅读下列程序说明和C++代码,将应填入(n)处的字句写在对应栏内。[说明]①定义私有数据成员code、english分别用于表示考生的编号、英语成绩,它们都是int型的数据。②完成成员函数voidStudent::inputinf
根据题意,图9-9中哪个文件可不必画出。根据题意,指出图9-10(B)中缺失的数据流的名称,并指出该数据流的起点和终点。
完成学生成绩管理子系统用例图。说明用例之间关联的选择原则。
阅读下列说明和有关图表,回答问题。【说明】(1)这是一个图书馆支持系统。(2)图书馆应用系统可以将图书和杂志借给借书者,这些借书者已经在系统中注册了,图书和杂志也已经注册过了。(3)图书馆负责新书的购买,一本流行图书会多买几
阅读以下预备知识、函数说明和C代码,将应填入(n)处的字句填写完整。[说明](1)对给定的字符集合及相应的权值,采用哈夫曼算法构造最优二叉树,并用结构数组存储最优二叉树。例如,给定字符集合{a,b,c,d)及其权值2、7、4、5,可构造如
阅读以下说明和C代码(代码13-4),将应填入(n)处的字句写在对应栏内。【说明】在一公文处理系统中,开发者定义了一个公文结构OfficeDoc,其中定义了公文应该具有的属性。当公文的内容或状态发生变化时,与之相关联的DocExplorer结构的值都
根据题干的[说明]及图1-11、图1-12的相关信息,类商品除了售出和缺货登记操作之外,还应具有哪些主要操作?(请使用[说明]中给出的词语回答问题)识别关联的多重度是面向对象建模过程中的一个重要步骤。请根据说明中给出的描述,将图1-11中(1)
阅读下列说明和图,回答问题1到问题3。[说明]目前大多数操作系统都采用虚拟存储技术,这样可在较小的可用内存中执行较大的用户程序,可在内存中容纳更多程序并发执行。引入虚拟存储技术,其基本思想是利用大容量的外存来扩充内存,产生一个
当在软件工程的环境中考虑风险时,主要基于Charette提出的3个概念。以下选项中不属于这3个概念的是(1)。项目风险关系项目计划的成败,(2)关系着软件的生存能力。在进行软件工程风险分析时,项目管理人员要进行4种风险评估活动,这4种活动分别是(3)以及确
随机试题
根据《水运工程工程量清单计价规范》(JTS/T271—2020),堆载预压的项目特征有()。
低碳钢管的水平固定上向焊引弧位置应在()位置。
什么是三级安全教育?
内科护理学在课程结束后采用百分制试卷的形式,对学生进行考核,用以了解学生是否已经达到了教学大纲所规定的目标。这属于()
凝固性坏死可能具有的形态特点是
可影响幼儿软骨发育,导致承关节损伤的药物是()。
2006年6月7日,我方以电报方式对美国甲公司发盘,在发盘的有效期内我方同时收到了甲公司的接受和撤回接受的通知,根据《联合国国际货物销售合同公约》规定,下列关于此项接受的说法正确的是()。
()主要负责制定应急和连续营业方案,识别关键业务程序,定期测试和检查灾难恢复和业务连续方案。
【2011年河南特岗.判断】气质影响人的活动方式与效率,是一个人选择职业的依据之一。()
公文的重要作用体现在六个方面:领导指导作用、准绳规范作用、联系沟通作用、宣传教育作用、商洽协商作用和()。
最新回复
(
0
)