信管网试题内容

试题内容

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

采用自底向上的方法实现该算法，则时间复杂度为（）。
A． O(n²)
B． O(n²lgn)
C． O(n³)
D． O(n2^)
A． O(n²)
B． O(n²lgn)
C． O(n³)
D． O(n2^)
查看答案