2. 从业资格
  3. 已知矩阵Am*n和Bn*p相乘的时间复杂度为O(mnp)。矩阵相乘满足结合律，如

已知矩阵Am*n和Bn*p相乘的时间复杂度为O(mnp)。矩阵相乘满足结合律，如

免费题库2022-08-02  29
问题 已知矩阵Am*n和Bn*p相乘的时间复杂度为O(mnp)。矩阵相乘满足结合律，如三个矩阵A、B、C相乘的顺序可以是(A*B)*C也可以是A*(B*C)。不同的相乘顺序所需进行的乘法次数可能有很大的差别。因此确定n个矩阵相乘的最优计算顺序是一个非常重要的问题。已知确定n个矩阵A1A2......An相乘的计算顺序具有最优子结构，即A1A2......An的最优计算顺序包含其子问题A1A2......Ak和Ak+1Ak+2……An（1≤k＜n）的最优计算顺序。可以列出其递归式为：其中，Ai的维度为pi-1*pi，m[i,j]表示AiAi+1……Aj最优计算顺序的相乘次数。先采用自底向上的方法求n个矩阵相乘的最优计算顺序。则求解该问题的算法设计策略为（　　）。算法的时间复杂度为（　　），空间复杂度为（　　）。给定一个实例，（p0p1……p5）=（20,15,4,10,20,25），最优计算顺序为（　　）。  问题1选项 A.分治法 B.动态规划法 C.贪心法 D.回溯法问题2选项 A.O(n2) B.O(n2lgn) C.O(n3) D.O(2^n)问题3选项 A.O(n2) B.O(n2lgn) C.O(n3) D.O(2^n)问题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)
选项
答案 BCAD
解析 第一空：本题提到“已知确定n个矩阵A1A2......An相乘的计算顺序具有最优子结构，即A1A2......An的最优计算顺序包含其子问题A1A2......Ak和Ak+1Ak+2……An（1≤k）的最优计算顺序”，即规模为n的问题的解与较小规模为k的问题的解有关，具有最优子结构，并且提到“m[i,j]表示AiAi+1……Aj最优计算顺序的相乘次数”即，用中间数组m[i,j]存放中间子结果，所以本题描述的算法策略是动态规划法，特点是具有最优子结构，并且会利用中间表记录中间结果，最后利用查表得到最优解。
第二空：题干给出“已知矩阵Am*n和Bn*p相乘的时间复杂度为O(mnp)”，即矩阵乘法的实现过程，可以简单理解为3层嵌套循环，所以时间复杂度为O(n^3)。
下面给出一个简单的矩阵乘法的代码段（只列出动态规划过程，具体变量声明已忽略）：

int cmm(int n,int p[]){

//n为矩阵个数，p[]为维度记录，本题n=5，p[]={20,15,4,10,20,25}

for(t=1;t for(i=0; i j=i+t ;
tempCost = -1;
for(k = i;k temp= m[k]+m[k+1][j]+p*p[k+1]*p[j+1] ;
if(tempCost==-1||tempCost>temp){
tempCost = temp;
tempTrace=k ;
}
}
m[j] = tempCost; //m[][]：二维数组，长度为n*n，其中元素m[j]表示Ai+1*Ai+2*…Aj+1的最优计算的计算代价

trace[j] = tempTrace; // trace[][]：二维数组，长度为n*n，其中元素trace[j]表示Ai+1*Ai+2*Aj+1的最优计算对应的划分位置，即k
}
}
return m[0][n-1]; //返回值为最优计算的计算代价，即乘法的次数

｝

第三空：本题在计算过程中，需要临时存储空间存放中间结果m[][]，二维数组占据空间为n*n，即空间复杂度为O(n^2)。

第四空：可以按照选项直接计算出相应乘法次数进行判断。
给定一个实例，（p0p1……p5）=（20,15,4,10,20,25）, 表示A1(20×15)，A2(15×4)，A3(4×10)，A4(10×20)，A5(20×25)。
选项A:(((A1×A2) ×A3) ×A4) ×A5，根据括号计算顺序，先计算A1×A2=A12(20×4)，乘法次数为20×15×4=1200；然后计算A12×A3=A123(20×10)，乘法次数为20×4×10=800；接着计算A123×A4=A1234(20×20)，乘法次数为20×10×20=4000；最后计算A1234×A5=A12345(20×25)，乘法次数为20×20×25=10000。

A选项乘法次数为1200+800+4000+10000=16000次；
选项A1×(A2×(A3×(A4×A5))) ，根据括号计算顺序，先计算A4×A5=A45(10×25)，乘法次数为10×20×25=5000；然后计算A3×A45=A345(4×25)，乘法次数为4×10×25=1000；接着计算A2×A345=A2345(15×25)，乘法次数为15×4×25=1500；最后计算A1×A2345=A12345(20×25)，乘法次数为20×15×25=7500。
B选项乘法次数为5000+1000+1500+7500=15000次；
C:((A1×A2)×A3)× (A4×A5) ，根据括号计算顺序，先计算A1×A2=A12(20×4)，乘法次数为20×15×4=1200；然后计算A12×A3=A123(20×10)，乘法次数为20×4×10=800；接着计算A4×A5=A45(10×25)，乘法次数为10×20×25=5000；最后计算A123×A45=A12345(20×25)，乘法次数为20×10×25=5000。
C选项乘法次数为1200+800+5000+5000=12000次；
选项D:(A1×A2) ×( (A3×A4)×A5) ，根据括号计算顺序，先计算A1×A2=A12(20×4)，乘法次数为20×15×4=1200；然后计算A3×A4=A34(4×20)，乘法次数为4×10×20=800；接着计算A34×A5=A345(4×25)，乘法次数为4×20×25=2000；最后计算A12×A345=A12345(20×25)，乘法次数为20×4×25=2000。
D选项乘法次数为1200+800+2000+2000=6000次；
D选项为最优计算顺序。
转载请注明原文地址:https://tihaiku.com/congyezige/2409602.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)