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

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

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

給定一個實例，(POPi……P5)=(20,15,4,10,20,25),最優(yōu)計算順序為( 4)。

(1)A、分治法

B、動態(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

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

相關(guān)推薦：

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

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

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