求解两个长度为n的序列X和Y的一个最长公共序列（如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA）可以采用多种计算方法。如可以采用蛮力法，对X的每一个子序列，判断其是否也是Y的子序列，
软考
软件设计师
2020-10-23 22:01:24
155
0
软件设计师真题解析2017年软考真题解析2017年软件设计师真题解析下半年软考真题解析上午软考真题解析计算机技术与软件专业技术资格（水平）考试软考真题解析
求解两个长度为n的序列X和Y的一个最长公共序列（如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA）可以采用多种计算方法。如可以采用蛮力法，对X的每一个子序列，判断其是否也是Y的子序列，最后求出最长的即可，该方法的时间复杂度为（ ）。经分析发现该问题具有最优子序列，可以定义序列成都分别为i和j的两个序列X和Y的最长公共子序列的成都为C[I,j]，如下式所示。(2017年软件设计师)
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)
参考答案：D A
参考解析：
版权声明
本文仅代表作者观点，不代表本站立场。
本文系作者授权发表，转载需标明出处。
如果您有更好的解答，欢迎留言评论。
评论