单选题
求解两个长度为n的序列X和Y的一个最长公共子序列（如序列ABCBDAB和 BDCABA的一个最长公共子序列为BCBA）可以采用多种计算方法。如可以采用蛮力法，对X的每一个子序列，判断其是否也是Y的子序列，最后求出最长的即可，该方法的时间复杂度为（ ）经分析发现该问题具有最优子结构，可以定义序列长度分别为i 和j的两个序列X和Y的最长公共子序列的长度为c[i,j]，如下式所示。
采用自底向上的方法实现该算法，则时间复杂度为（ ）。
问题1选项
A.O(n 2)
B.O(n 2lgn)
C.O(n 3)
D.O(n2 n)
A.O(n 2)
B.O(n 2lgn)
C.O(n 3)
D.O(n2 n)
问题2选项
A.O(n 2)
B.O(n 2lgn)
C.O(n 3)
D.O(n2 n)
A.O(n 2)
B.O(n 2lgn)
C.O(n 3)
D.O(n2 n)
相关知识点试题
相关试卷
咨询
查看视频解析
