首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知矩阵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
45
问题
已知矩阵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
软件设计师上午基础知识考试
软考中级
相关试题推荐
【说明】某公司要开发一个销售管理系统,该系统的主要功能是:处理客户和销售员送来的订单;工厂是根据订货安排生产的,交出货物同时开出发票,收到客户付款后,根据发票存根进行应收款处理。每张订单由订单号,若干头信息和订单细节组成。一张订单可定购多种产品,工厂对大
下面是快速排序的伪代码,请将空缺处(1)~(3)的内容填写完整。伪代码中的主要变量说明如下。A:待排序数组p,r:数组元素下标,从p到rq:划分的位置x:枢轴元素i:整型变量,用于描述数组下标。下标小于或等于i的元素
数据流图13-6中有两条数据流是错误的,请指出这两条数据流的起点和终点。根据系统功能和数据流图填充下列数据字典条目中的(1)和(2):查询请求信息=[查询读者请求信息|查询图书请求信息]读者情况=读者号+姓名+所在单位+{借书情况}管理工作请求单
根据以上说明设计的E—R图如图6—3所示,请指出地址簿与用户、电子邮件账号与邮件、邮件与附件之间的联系类型。(1)请指出[问题2]中给出的地址簿、邮件和附件关系模式的主键,如果关系模式存在外键请指出。(2)附件属于弱实体吗?请用50字以内的文字说明
阅读下列说明和图,回答问题1到问题3,将解答填入对应栏内。[说明]操作系统中,死锁(Deadlock)是指多个进程在运行的过程中因争夺资源而造成的一种僵局。当进程处于这种僵持状态时,若无外力作用,它们都将无法再向前推进。面对死锁
不考虑数据确认处理(加工2),请指出图3-17~图3-19数据流图中可能存在的错误。请使用[说明]中数据字典条目定义形式,将以下(1)和(2)空缺处的内容填写完整。初录数据=(1)复录数据=(2)
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】对有向图进行拓扑排序的方法是:(1)初始时拓扑序列为空:(2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该顶点出发的弧;(3)重复(2),
ARP协议的作用是(61),ARP报文封装在(62)中传送。
多媒体技术的关键在于解决动态图像和声音的存储与传输问题。若不经压缩,以 VGA640×480点阵存储一幅256色的彩色图像大约需(56)MB存储空间,以9600bit/s的速度传输这幅图像大约需(57)秒,按我国电视PAL标准每秒25幅,一张650MB的光
在比较常见的公共传输系统中,(32)是以模拟技术为基础的电路交换网络;(33)是基于城域网协议的包交换公共数据网络;(34)提供基于线路交换的端到端的数字连接通道。帧中继的典型速率范围是(35)。
随机试题
若有关系模式:部门(部门号,部门名),其中部门号为主键,则下列一定无法完成的操作是________。
Lazinessisasin.Everyoneknowsthat.Wehaveprobablyallhadlecturespointingoutthatlazinessisimmoral,thatitiswast
在有一定密度的森林内,随着时间的推移,森林内植物的株数和生长发生速率会不断减小,这种现象叫做______。
肝的库普弗细胞位于_______,具有_______功能,贮脂细胞位于_______,具有_______和_______功能。
男性,36岁,因胃穿孔行急诊手术。术后第6天出现发热、寒战、右上腹痛及呃逆。查体:右肺呼吸音低,呼吸移动减弱,胸片示右膈活动受限,肋膈角不清。白细胞18.1×109/L。此病人应诊断为
属于DR成像直接转换方式的部件是
用直线切割一个有限平面,后一条直线与此前每条直线都要产生新的交点。第1条直线将平面分成2块,第2条直线将平面分成4块,第3条直线将平面分成7块,按此规律将该平面分为22块需:
小麦:馒头
设F1(x)与F2(x)分别为随机变量X1与X2的分布函数,为了使F(x)=aF1(x)一bF2(x)是某随机变量的分布函数,在下列给定的各组数值中应取()
请用400字以内文字,分别论述原型法与严格定义法适用的场合。原型生命周期提供了一种用原型法完成需求定义的完整方法。但对于一些特殊情况,如规模较小,完整性要求较弱的应用,可以采取灵活的做法以适应实际目标。请用300字以内文字,说明改变原型生命周期约束的
最新回复
(
0
)