首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知矩阵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
21
问题
已知矩阵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)。
(63)
选项
A、O(n2)
B、O(n2lgn)
C、O(n3)
D、O(2n)
答案
C
解析
转载请注明原文地址:https://kaotiyun.com/show/JUCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读以下关于工作流系统模型建立和性能分析的叙述,根据要求回答问题1~问题4。[说明]某软件开发公司向客户交付系统产品后,由技术支持部门负责向客户提供技术服务。该技术支持部门的业务流程如下:①当该技术支持部门接到一个客户问询电话时,由
根据以上[说明]设计的实体联系图(E-R图)如图7-12所示,请指出读者与图书、书目与读者、书目与图书之间的联系类型。该图书管理系统的主要关系模式如下,请将“借还记录”和“预约登记”关系中的(7)、(8)空缺处的内容填写完整。管理员(工号,姓
在(1)空缺处填入所需的实体、联系及其属性,完成概念模型设计。如果允许企业通过互联网修改本企业的基本信息,应对数据库的设计做哪些修改?请用200字以内的文字叙述实现方案。[附]关系模式的标记规则如下:关系名(属性名1,属性名2,
ASP属于服务器端方案还是客户端方案?ASP的工作原理图中(1)、(2)应是什么?请至少写出ASP的5个特点。
不考虑数据确认处理(加工2),请指出图3-17~图3-19数据流图中可能存在的错误。请使用[说明]中数据字典条目定义形式,将以下(1)和(2)空缺处的内容填写完整。初录数据=(1)复录数据=(2)
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某网上药店允许顾客凭借医生开具的处方,通过网络在该药店购买处方上的药品。该网上药店的基本功能描述如下:(1)注册。顾客在买药之前,必须先在网上药店注册。注册过程中需填写顾客资料
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】在一块电路板的上下两端分别有n个接线柱。根据电路设计,用(i,π(i))表示将上端接线柱i与下端接线柱Ⅱ(i)相连,称其为该电路板上的第i条连线。如图4.1所示的π(i)排列
(2012年下半年下午试题二)阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某会议策划公司为了方便客户,便于开展和管理各项业务活动,需要构建一个基于网络的会议预定系统。【需求分析】(1)会
原型化方法是一类动态定义需求的方法,(44)不是原型化方法所具有的特征。与结构化方法相比,原型化方法更需要(45)。衡量原型开发人员能力的重要标准是(46)。
在比较常见的公共传输系统中,(32)是以模拟技术为基础的电路交换网络;(33)是基于城域网协议的包交换公共数据网络;(34)提供基于线路交换的端到端的数字连接通道。帧中继的典型速率范围是(35)。
随机试题
在我国卫生法律体系中,《医疗事故处理条例》、《中医药条例》等规范性文件属于
痫病与五脏均有关联,但主要责之于()
随着国际经济文化一体化的进展,中国与世界各国的药品贸易日渐增多。在中国药品标准的国际化进程中,了解国外的药典十分重要。目前,国际上有代表性的药典有《美国药典》《英国药典》《欧洲药典》和《日本药典》。《欧洲药典》最新版生效日期为()。
A.红细胞/血红蛋白减少B.中性粒细胞增多C.嗜酸性粒细胞减少D.血小板增多E.嗜碱性粒细胞增多细菌感染患者可出现
债务人对支付令的异议
公允价值,是指市场参与者在计量日发生的有序交易中,出售一项资产所能收到或者转移一项负债所需支付的价格。()
根据《票据法》规定,下列各项中,属于支票必须记载的事项包括()。
意志的基本品质是()
简述侵犯公民个人信息罪的构成要件。
CrimeCyclesThroughouttheYearCrimehasitsowncycles,amagazinereportedsomeyearsage.Policerecordsthatwerestudied
最新回复
(
0
)