两个矩阵Amn和Bnn相乘，用基本的方法进行，则需要的乘法次数为mnp。多个矩阵相乘满足结合律，不同的乘法顺序所需要的乘法次数不同。考虑采用动态规划方法确定Mi，M(i+1)，…，Mj多个矩阵连乘的最优顺序，即所需要的乘法次数最少。最少乘法次数用m

admin2019-07-12 46

问题两个矩阵A_m*n和B_n*n相乘，用基本的方法进行，则需要的乘法次数为m*n*p。多个矩阵相乘满足结合律，不同的乘法顺序所需要的乘法次数不同。考虑采用动态规划方法确定M_i，M_(i+1)，…，M_j多个矩阵连乘的最优顺序，即所需要的乘法次数最少。最少乘法次数用m[i,j]表示，其递归式定义为：

其中，i、j和k为矩阵下标，矩阵序列中M_i的维度为(p_i-1)*p_i。采用自底向上的方法实现该算法来确定n个矩阵相乘的顺序，其时间复杂度为(1)。若四个矩阵M₁、M₂、M₃、M₄相乘的维度序列为2、6、3、10、3，采用上述算法求解，则乘法次数为(2)。
(1)

选项 A、O(n²)
B、O(n²lgn)
C、O(n³)
D、O(n³lgn)

答案C

解析

转载请注明原文地址:https://www.kaotiyun.com/show/jQCZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

软件设计师上午基础知识考试

软考中级

该程序的控制流图中A～E分别是什么?为各测试路径设计测试用例。

阅读以下说明和JAVA2代码，填入(n)处的。[说明]以下JAVA程序实现了在接口interfaceiShape2D的定义和应用，仔细阅读代码和相关注释，将程序补充完整。[代码6-1]interfaceiShape2D

阅读下列函数说明和C代码，应填入(n)处。[说明]假设设A和B均为顺序表，A’和B’分别为A和B中除去最大共同前缀后的子表(例如，A=(x，y，y，z，x，z)，B=(x，y，y，z，y，x，x，z)，则两者中最大的共同前缀为(x，y，y

阅读以下说明，回答问题，将解答填入对应的解答栏内。[说明]给出一个接收三个数a、b、c作为三角形边长并输出三角形的类型的程序。程序代码如下所示：结点源代码行Areada,b,cB

利用存在的依赖关系构造一个图书馆的对象模型。画出上一问中使用的图书馆程序的层次结构图。

利用存在的依赖关系构造一个图书馆的对象模型。张三到图书馆借阅一本书，两个月后，他把这本逾期的书返还给图书馆。画出这个场景的时序图。

(1)请说明流程图中的文件F0、F1分别是哪个文件。(2)处理1和处理5分别按照哪些数据项进行分类?处理4能发现哪些错误(不需考虑设备故障错误)?

在市场规制法领域，属于经济法经济目标的是【】

Wegotupearlythismorningand【C1】alongwalkafterbreakfast.Wewalked【C2】thebusinesssectionofthecity.Ito

A、implyB、fryC、specifyD、varyD选项D画线字母读[i]，其他选项画线字母读[ai]。

M蛋白的实质是

乙类物品运输车的汽车库建筑最多为()层，且应独立建造。

设a，b，c，∈R+，则“abc=1”是“≤a+6+c”的()．

科学家诺贝尔为了研究炸药，不顾自己生命危险进行实验。在一次试验中，爆炸空前猛烈，浓烈烟雾冲天，诺贝尔从烟雾中冲出，满脸鲜血淋漓，但他却发疯似地高喊：“我成功了!我成功了!”这属于()。

我国最大的平原是()。

对数据对象施加封锁，可能会引起活锁和死锁。预防死锁通常有______和顺序封锁法两种方法。

软件设计师上午基础知识考试

软考中级

该程序的控制流图中A～E分别是什么?为各测试路径设计测试用例。

阅读以下说明和JAVA2代码，填入(n)处的。[说明]以下JAVA程序实现了在接口interfaceiShape2D的定义和应用，仔细阅读代码和相关注释，将程序补充完整。[代码6-1]interfaceiShape2D

阅读下列函数说明和C代码，应填入(n)处。[说明]假设设A和B均为顺序表，A’和B’分别为A和B中除去最大共同前缀后的子表(例如，A=(x，y，y，z，x，z)，B=(x，y，y，z，y，x，x，z)，则两者中最大的共同前缀为(x，y，y

阅读以下说明，回答问题，将解答填入对应的解答栏内。[说明]给出一个接收三个数a、b、c作为三角形边长并输出三角形的类型的程序。程序代码如下所示：结点源代码行Areada,b,cB

利用存在的依赖关系构造一个图书馆的对象模型。画出上一问中使用的图书馆程序的层次结构图。

利用存在的依赖关系构造一个图书馆的对象模型。张三到图书馆借阅一本书，两个月后，他把这本逾期的书返还给图书馆。画出这个场景的时序图。

(1)请说明流程图中的文件F0、F1分别是哪个文件。(2)处理1和处理5分别按照哪些数据项进行分类?处理4能发现哪些错误(不需考虑设备故障错误)?

在市场规制法领域，属于经济法经济目标的是【】

Wegotupearlythismorningand【C1】______alongwalkafterbreakfast.Wewalked【C2】______thebusinesssectionofthecity.Ito

A、implyB、fryC、specifyD、varyD选项D画线字母读[i]，其他选项画线字母读[ai]。

M蛋白的实质是

乙类物品运输车的汽车库建筑最多为()层，且应独立建造。

设a，b，c，∈R+，则“abc=1”是“≤a+6+c”的()．

科学家诺贝尔为了研究炸药，不顾自己生命危险进行实验。在一次试验中，爆炸空前猛烈，浓烈烟雾冲天，诺贝尔从烟雾中冲出，满脸鲜血淋漓，但他却发疯似地高喊：“我成功了!我成功了!”这属于()。

我国最大的平原是()。

对数据对象施加封锁，可能会引起活锁和死锁。预防死锁通常有______和顺序封锁法两种方法。

Wegotupearlythismorningand【C1】alongwalkafterbreakfast.Wewalked【C2】thebusinesssectionofthecity.Ito