信管网试题内容

试题内容

已知矩阵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＜n）的最优计算顺序。
可以列出其递归式为：

其中，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)
查看答案