信管网综合知识

求解两个长度为n的序列X和Y的一个最长公共序列(如序列 ABCBDAB和 BDCABA 的一个最长公共子序列为 BCBA) 可以采用多种计算方法。如可以采用蛮力法，对X的每一个子序列， 判断其是否也是Y的子序列，最后求出最长的即可，该方法的时间复杂度为( 1 ) 。 经分析发现该问题具有最优子序列，可以定义序列成都分别为i和j的两个序列X和Y的最长公共子序列的成都为C[I,j]，如下式所示。

采用自底向上的方法实现该算法，则时间复杂度为( 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^)

信管网参考答案：D、A

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

相关推荐：

点击查看/下载：软件设计师历年真题汇总

点击查看：软件设计师在线培训课程 丨 免费试听课程

免费练习：软件设计师考试题库(模拟试题、章节练习、每日一练)