已知矩陣Am*n和Bn*p相乘的時(shí)間復(fù)雜度為O(mnp)。矩陣相乘滿足結(jié)合律，如三個(gè)矩陣A、B、C相乘的順序可以是(A*B)*C也可以是A*(B*C)。不同的相乘順序所需進(jìn)行的乘法次數(shù)可能有很大的差別。因此確定n個(gè)矩陣相乘的最優(yōu)計(jì)算順序是一個(gè)非常重要的問題。已知確定n個(gè)矩陣A,A2、、、、、、An相乘的計(jì)算順序具有最優(yōu)子結(jié)構(gòu)，即A1A2、、、、、、An的最優(yōu)計(jì)算順序包含其子問題A1A2、、、、、、Ak和Ak+1Ak+2……An(l<=k 可以列出其遞歸式為：

其中，Ai的維度為pi-1*pim[i，j]表示AiAi+1……Aj最優(yōu)計(jì)算順序的相乘次數(shù)。

先采用自底向上的方法求n個(gè)矩陣相乘的最優(yōu)計(jì)算順序。則求解該問題的算法設(shè)計(jì)策略為( 1)。算法的時(shí)間復(fù)雜度為(2 )，空間復(fù)雜度為( 3)。

給定一個(gè)實(shí)例，(POPi……P5)=(20,15,4,10,20,25),最優(yōu)計(jì)算順序?yàn)? 4)。

(1)A、分治法

B、動(dòng)態(tài)規(guī)劃法

C、貪心法

D、回溯法

(2)A、O(n2)

B、O(n2lgn)

C、O(n3)

D、O(2n)

(3)A、O(n2)

B、O(n2lgn)

C、O(n3)

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)

信管網(wǎng)參考答案：B、C、A、D

查看解析：m.xiexiliangjiufa.com/st/4170727775.html

相關(guān)推薦：

點(diǎn)擊查看/下載：軟件設(shè)計(jì)師歷年真題匯總

點(diǎn)擊查看：軟件設(shè)計(jì)師在線培訓(xùn)課程 丨 免費(fèi)試聽課程

免費(fèi)練習(xí)：軟件設(shè)計(jì)師考試題庫(模擬試題、章節(jié)練習(xí)、每日一練)