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

admin2019-07-12 56

问题两个矩阵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)中只有一个外部实体E1。使用【说明】中的词语，给出E1的名称。使用【说明】中的词语，给出图(b)中的数据存储D1～D4的名称。

若这三个事务允许并行执行，则请列举出有多少可能的正确结果。各个事务的内部结构如下所示。若事务不施加任何锁，则有多少可能的调度。T1:R1(GetAintot1;t1:=t1+1);U1(UpdateAfromt1);

指出哪张图的哪个文件可以不必画出。指出数据流图4-1和数据流图4-2中错误的数据流。

在需求分析阶段，采用UML的用例图描述系统功能需求，如图1-6所示。指出图1-6中(1)(2)、(3)、(4)分别是哪个用例?图1-7采用协作图描述借书和还书两个动态过程的交互关系。在UML中，重复度(multiplicity)定义了某个实体的一个实例

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

阅读下列函数说明和C代码，将应填入(n)处的字句写在的对应栏内。请根据算法的C代码，分析此算法效率。

放射性同位素测井可以用来判断油管外窜槽()

北京犬，发病1周，包皮肿胀，包皮口污秽不洁、流出脓样腥臭液体；翻开包皮囊，见红肿、溃疡病变。该病是()。

在计算机中为了用二进制编码表示英文字母、符号、阿拉伯数字等，应用最广泛、具有国际标准的是()。

对于期货价格的理解，下列说法正确的有()。

Ahouseisthemostexpensivethingmostpeoplewilleverbuy.Veryfewpeoplehaveenoughmoneyoftheirowntobuyahouse,so

2013年1月4日《人民日报》发表文章《“中国梦”：内涵.路径.保障》指出：“实现中华民族伟大复兴，就是中华民族近代以来最伟大的梦想。”实现“中国梦”的科学道路是()。

中国古代记载文字的器物曾经有：①竹简，②青铜器，③帛书，④甲骨，⑤纸张。它们在历史上出现的先后顺序是：

生产方式

Inthesecondhalfofeachyear,manypowerfulstormsareborninthetropicalAtlanticandCaribbeanseas.Of【1】,onlyaboutha