软题库 培训课程
当前位置:信管网 >> 在线考试中心 >> 软件设计师题库 >> 试题查看
试卷年份2017年下半年
试题题型【单选题】
试题内容

求解两个长度为 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^)

查看答案

相关试题