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

admin2019-07-12 36

问题两个矩阵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)

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

软考中级

阅读以下说明和c++码，将应填入(n)处的字名写在的对应栏内。[说明]以下函数完成求表达式的值，请填空使之完成此功能。floatsum(floatx){floats=0.0;ints

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

该程序的控制流图中A～E分别是什么?用基本路径覆盖法给出测试路径。

阅读以下说明和流程图(如图1所示)，回答问题1至问题4。【说明】本流程图是将中缀表示的算术表达式转换成后缀表示。如中缀表达式(A-(BC+D)E)/(F+G))的后缀表示为ABCD+E-FG+/为了方

指出哪张图的哪个文件可以不必画出。根据题中说明和数据流图分析，“查询处理”是否可以查询出剩余票的信息?为什么?

阅读以下说明和VisualBasic码，将应填入(n)处的字名写在对应栏内[说明]设计一个计时程序。该程序用户界面由一个文本框(text1)，两个按钮——命令按钮1(Command1)按钮、命令按钮(Command2)组成。程序运行后，用

根据题意，给出“自动售票机”类的主要属性。根据题中所述术语，指出图9-19中状态1到状态4分别是什么?

阅读以下关于某订单管理系统的技术说明、部分UML类图及Java程序，将Java程序中(1)～(5)空缺处的语句填写完整。[说明]某订单管理系统的部分UML类图如图5-16所示。在图5-16中，Product表示产品，Pro

下列观念中，造成中国文化中整体系统、辩证发展思维方式的观念是()

A．决明子B．乌梅C．草果D．沙苑子E．枸杞子菱状方形或短圆柱形，两端平行倾斜，表面绿棕色，平滑有光泽，气微，味微苫()

小儿，3岁，于入院前曾与水痘患儿接触，应采取的措施是()

股票是一种资本证券，属于()。

有限责任公司的股东人数为()。

2011年1～9月，全国造船完工5101万载重吨，同比增长18．3％，9月当月完工786万载重吨，环比增长67．2％，新承接船舶订单规模2902万载重吨，同比下降42．8％，手持船舶订单规模16886万载重吨，同比下降13．8％，比2010年底下降14．5

Excerpt1Teachingisunquestionablyoneofthemostimportantcommitmentsonecanmakeforthefutureeconomicprosperityo

2

Persons’remarksarementionedatthebeginningofthetextto_____.WhichofthefollowingstatementsisTRUEaccordingtoth

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

软考中级

阅读以下说明和c++码，将应填入(n)处的字名写在的对应栏内。[说明]以下函数完成求表达式的值，请填空使之完成此功能。floatsum(floatx){floats=0.0;ints

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

该程序的控制流图中A～E分别是什么?用基本路径覆盖法给出测试路径。

阅读以下说明和流程图(如图1所示)，回答问题1至问题4。【说明】本流程图是将中缀表示的算术表达式转换成后缀表示。如中缀表达式(A-(B*C+D)*E)/(F+G))的后缀表示为ABC*D+E*-FG+/为了方

指出哪张图的哪个文件可以不必画出。根据题中说明和数据流图分析，“查询处理”是否可以查询出剩余票的信息?为什么?

阅读以下说明和VisualBasic码，将应填入(n)处的字名写在对应栏内[说明]设计一个计时程序。该程序用户界面由一个文本框(text1)，两个按钮——命令按钮1(Command1)按钮、命令按钮(Command2)组成。程序运行后，用

根据题意，给出“自动售票机”类的主要属性。根据题中所述术语，指出图9-19中状态1到状态4分别是什么?

阅读以下关于某订单管理系统的技术说明、部分UML类图及Java程序，将Java程序中(1)～(5)空缺处的语句填写完整。[说明]某订单管理系统的部分UML类图如图5-16所示。在图5-16中，Product表示产品，Pro

下列观念中，造成中国文化中整体系统、辩证发展思维方式的观念是()

A．决明子B．乌梅C．草果D．沙苑子E．枸杞子菱状方形或短圆柱形，两端平行倾斜，表面绿棕色，平滑有光泽，气微，味微苫()

小儿，3岁，于入院前曾与水痘患儿接触，应采取的措施是()

股票是一种资本证券，属于()。

有限责任公司的股东人数为()。

Excerpt1Teachingisunquestionablyoneofthemostimportantcommitmentsonecanmakeforthefutureeconomicprosperityo

2

Persons’remarksarementionedatthebeginningofthetextto_____.WhichofthefollowingstatementsisTRUEaccordingtoth

阅读以下说明和流程图(如图1所示)，回答问题1至问题4。【说明】本流程图是将中缀表示的算术表达式转换成后缀表示。如中缀表达式(A-(BC+D)E)/(F+G))的后缀表示为ABCD+E-FG+/为了方