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

admin2019-07-12 52

问题两个矩阵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://kaotiyun.com/show/jQCZ777K

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

使用说明中的词语，给出上述顶层数据流图中的外部实体E1～E4的名称。使用说明中的词语，给出上述0层数据流图中的数据存储D1～D3的名称。

填充流程图中①的判断条件。中缀表达式(A+B-CD)(E-F)/G经该流程图处理后的输出是什么?[*]

阅读下列程序和控制流图，将应填入(n)的字句写在答题纸的对应栏内。【程序】下面是一段求最大值的程序，其中datalist是数据表，n是datalist的长度+intGetMax(intn,intdatalist[])

指出哪张图的哪些文件可以不必画出。根据系统功能和数据流图填充下列数据字典条目中的(1)和(2)：试题得分表二准考证号+{课程名+成绩}考生名册=报名号+准考证号+姓名+通信地址+出生年份+文化程度+职业考生通知单=(1)

依据说明，完成下面的类图，要求第1层和第2层填写标识、主要属性和操作，第3层填写标识即可。UML规定类图中类之间的关系有关联、聚集、继承，请说明它们的含义和之间的区别。

下列各项，与海藻相反的药物是

A．CVP很低，尿量多B．CVP偏低，尿量少C．CVP偏低，尿量多D．CVP偏高，尿量多E．CVP很高，尿量少说明液体已补足()

津液的输布障碍与()脏腑功能失常有关。

民用建筑很少使用的保温隔热材料是()。

对仓库中的所有存货进行盘点属于全面清查。()

经济法是调整宏观经济调控关系和市场规制关系的法律规范的总称。()

2008年北京奥运会五个拟人化的吉祥物的原型分别是()。

“根据辩证唯物主义的基本原理，我们要坚持理论和实践相统一，必须反对教条主义和实用主义”，这是因为（）。

Languageis,andshouldbe,alivingthing,constantlyenrichedwithnewwordsandformsofexpression.Butthereisavitaldis

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

软考中级

使用说明中的词语，给出上述顶层数据流图中的外部实体E1～E4的名称。使用说明中的词语，给出上述0层数据流图中的数据存储D1～D3的名称。

填充流程图中①的判断条件。中缀表达式(A+B-C*D)*(E-F)/G经该流程图处理后的输出是什么?[*]

阅读下列程序和控制流图，将应填入(n)的字句写在答题纸的对应栏内。【程序】下面是一段求最大值的程序，其中datalist是数据表，n是datalist的长度+intGetMax(intn,intdatalist[])

指出哪张图的哪些文件可以不必画出。根据系统功能和数据流图填充下列数据字典条目中的(1)和(2)：试题得分表二准考证号+{课程名+成绩}考生名册=报名号+准考证号+姓名+通信地址+出生年份+文化程度+职业考生通知单=(1)

依据说明，完成下面的类图，要求第1层和第2层填写标识、主要属性和操作，第3层填写标识即可。UML规定类图中类之间的关系有关联、聚集、继承，请说明它们的含义和之间的区别。

下列各项，与海藻相反的药物是

A．CVP很低，尿量多B．CVP偏低，尿量少C．CVP偏低，尿量多D．CVP偏高，尿量多E．CVP很高，尿量少说明液体已补足()

津液的输布障碍与()脏腑功能失常有关。

民用建筑很少使用的保温隔热材料是()。

对仓库中的所有存货进行盘点属于全面清查。()

经济法是调整宏观经济调控关系和市场规制关系的法律规范的总称。()

2008年北京奥运会五个拟人化的吉祥物的原型分别是()。

“根据辩证唯物主义的基本原理，我们要坚持理论和实践相统一，必须反对教条主义和实用主义”，这是因为（）。

Languageis,andshouldbe,alivingthing,constantlyenrichedwithnewwordsandformsofexpression.Butthereisavitaldis

填充流程图中①的判断条件。中缀表达式(A+B-CD)(E-F)/G经该流程图处理后的输出是什么?[*]