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

采用自底向上的方法實現(xiàn)該算法，則時間復雜度為( 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.jazzmuze.com/st/3954929299.html

相關推薦：

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

點擊查看：軟件設計師在線培訓課程 丨 免費試聽課程

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