求解兩個(gè)長(zhǎng)度為n的序列X和Y的一個(gè)最長(zhǎng)公共序列(如序列 ABCBDAB和 BDCABA 的一個(gè)最長(zhǎng)公共子序列為 BCBA) 可以采用多種計(jì)算方法。如可以采用蠻力法，對(duì)X的每一個(gè)子序列， 判斷其是否也是Y的子序列，最后求出最長(zhǎng)的即可，該方法的時(shí)間復(fù)雜度為( 1 ) 。 經(jīng)分析發(fā)現(xiàn)該問題具有最優(yōu)子序列，可以定義序列成都分別為i和j的兩個(gè)序列X和Y的最長(zhǎng)公共子序列的成都為C[I,j]，如下式所示。

采用自底向上的方法實(shí)現(xiàn)該算法，則時(shí)間復(fù)雜度為( 2 )。

(1)A.O(n²)

B.O(n²lgn)

C.O(n³)

D.O(n2^)

(2)A.O(n²)

B.O(n²lgn)

C.O(n³)

D.O(n2^)

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

查看解析：www.shc2b.com/st/3954929299.html

相關(guān)推薦：

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

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

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