求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCA

最全题库2022-08-02  44

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

选项

答案 DA

解析 1.X、Y的所有子序列都检查过后即可求出X、Y的最长公共子序列。X的一个子序列相应于下标序列1,2,…,n的一个子序列。因此,X共有2n个子序列。当然,Y也有2m个子序列。判断一个子序列是否也是Y的子序列的时间是n,因此时间复杂度为O(n2n)
2.动态规划的一个计算最长公共子序列的方法如下,两个序列X、Y:
设有二维数组c[j]表示X的i位和Y的j位之前的最长公共子序列的长度,则有题干给定的函数表现形式:
其中,c(i,j)当X的第i位与Y的第j位完全相同时为”1“,否则为”0“。
此时,c[j]中最大的数便是X和Y的最长公共子序列的长度,依据该数组回溯,便可找出最长公共子序列。该算法的空间、时间复杂度均为O(n2)。
转载请注明原文地址:https://tihaiku.com/congyezige/2410404.html

最新回复(0)