首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知矩阵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
32
问题
已知矩阵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)。
(62)
选项
A、分治法
B、动态规划法
C、贪心法
D、回溯法
答案
B
解析
转载请注明原文地址:https://kaotiyun.com/show/DUCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列C程序和程序说明,将应填入(n)处的字句写在答题纸的对应栏内。【说明】用克鲁斯卡尔算法求解给定图的最小生成树。#include<stdio.h>#include<stdlib.h>#defineMAXN30
假设当前该旅馆各个房间的情况见表3。当输入M=4,R=0时,该算法的输出是什么?如果限制该算法最多输出K个可供选择的房间号,则在流程图1的。所指的判断框应改成什么处理?
根据要求将SQL语句补充完整。(1)查询各系的学生数SELECT(1),COUNT(*)(2)GROUPBYDEPTNO;(2)更改课程号为C601的课程名为“大学物理”UPDATE(3)SET(4)(3)基于学生信息表,
阅读下列说明和数据流图,回答问题1至问题3。【说明】某供销系统接受顾客的订货单,当库存中某配件的数量小于订购量或库存量低于一定数量时,向供应商发出采货单;当某配件的库存量大于或等于订购量时,或者收到供应商的送货单时并更新了库存后,向顾客发出提
阅读以下说明和图,回答问题1~问题3,将解答写在对应栏内。[说明]通行费征收计算机管理系统包括收费部门业务活动管理和固定资产管理两大功能。收费部门采取站(库)、队、收费员三级管理模式。站是一个基层收费单位,由几个征收队组成,收费员是
下面是一个Applet程序,其功能是在绘图区域中通过鼠标的移动来绘制直线,并且有清除绘图区域按钮,用来清除已经绘制的图像。程序运行结果如图5所示。importjava.awt.*;importjava.applet.*;
请将图3-25中的(1)~(3)空缺处的内容填写完整。假设有6个作业job1,job2,…,job6;完成作业的收益数组p=(p[1],p[2],p[3],p[4],p[5],p[6])=(90,80,50,30,20,10);每个作业
不考虑数据确认处理(加工2),请指出图3-17~图3-19数据流图中可能存在的错误。请使用[说明]中数据字典条目定义形式,将以下(1)和(2)空缺处的内容填写完整。初录数据=(1)复录数据=(2)
在某超市里有一个收银员,且同时最多允许有n个顾客购物,我们可以将顾客和收银员看成是两类不同的进程,且工作流程如图1所示。为了利用PV操作正确地协调这两类进程之间的工作,设置了三个信号量S1、S2和Sn,且初值分别为0、0和n。这样图中的a应填写(17),图
软件开发的螺旋模型综合了瀑布模型和演化模型的优点,还增加了(20)。采用螺旋模型时,软件开发沿着螺线自内向外旋转,每转一圈都要对(21)进行识别和分析,并采取相应的对策。螺旋线第一圈的开始点可能是一个(22)。从第二圈开始,一个新产品开发项目开始了,新产品
随机试题
下列关于房产税计税依据的说法,正确的有()。
引起医院感染的病原微生物主要是
有关人力资源管理的工作有:①员工的培训;②员工的定向;③编制人力资源规划;④员工的绩效考评;⑤通过招聘增补员工;⑥通过解聘减少员工;⑦员工的业务提高。请选择出正确的工作步骤是( )。
在物资采购管理工作中,编制采购计划后进行的工作是()。
“产品成本”项目一般包括()。
我国帝王陵墓中随葬陶俑最多的是()。
在SQLServer2008中,常常会发生数据库数据过大的情况,此时则需要对表进行处理,通常可采用人工分割表的方法优化性能。下列有关分割表的说法,错误的是()
下面是一个Applet程序,其功能是统计输入字符串中的每个字符在该串中出现的次数。要求,窗口中有一个文本框作为输入,一个按钮,点击则进行统计,统计结果以图形方式输出。请改正程序中的错误(有下画线的语句),使程序能输出正确的结果。注意:不改动程序的结
Thecuriouslookfromthestrangersaroundhermadeherfeeluneasy.
【B1】【B8】
最新回复
(
0
)