信管网综合知识

已知矩阵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*pim[i，j]表示AiAi+1……Aj最优计算顺序的相乘次数。

先采用自底向上的方法求n个矩阵相乘的最优计算顺序。则求解该问题的算法设计策略为( 1)。算法的时间复杂度为(2 )，空间复杂度为( 3)。

给定一个实例，(POPi……P5)=(20,15,4,10,20,25),最优计算顺序为( 4)。

(1)A、分治法

B、动态规划法

C、贪心法

D、回溯法

(2)A、O(n²)

B、O(n²lgn)

C、O(n³)

D、O(2n)

(3)A、O(n²)

B、O(n²lgn)

C、O(n³)

D、O(2n)

(4)A、(((A1*A2)*A3)*A4)*A5

B、A1*(A2*(A3*(A4*A5)))

C、((A1*A2)*A3)*(A4*A5)

D、(A1*A2)*((A3*A4)*A5)

信管网参考答案：B、C、A、D

查看解析：www.cnitpm.com/st/4170727775.html

相关推荐：

点击查看/下载：软件设计师历年真题汇总

点击查看：软件设计师在线培训课程 丨 免费试听课程

免费练习：软件设计师考试题库(模拟试题、章节练习、每日一练)