2. 计算机
  3. 求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。 经分析发现该问题具有最优子结构，可以定义序列长度分别为i和j的两个序列X和Y的最长公共子序列的长度为c[i,j]，

求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。 经分析发现该问题具有最优子结构，可以定义序列长度分别为i和j的两个序列X和Y的最长公共子序列的长度为c[i,j]，

admin2018-11-21  80
问题 求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。
经分析发现该问题具有最优子结构，可以定义序列长度分别为i和j的两个序列X和Y的最长公共子序列的长度为c[i,j]，如下式所示。

采用自底向上的方法实现该算法，则时间复杂度为_____________。
选项 A、O(n2)
B、O(n2lgn)
C、O(n3)
D、O(n2n)
答案A
解析 本题考查算法设计与分析的基本知识。要求考生熟悉典型的算法设计技术及其典型的问题的求解。
    应用蛮力法求解最长公共子序列时，其思路在题干已经给出。对X的每一个子序列，判断其是否也是Y的子序列，那么长度为n的序列X的子序列数是2n，而判断一个子序列是否也是Y的子序列的时间是n，因此时间复杂度为O(n2n)。
    而采用动态规划自底向上的方法求解时，题干也给出了最优子结构和递归式的定义，因此很容易看出算法的时间复杂度实际上就是i和j的两重循环，时间复杂度为O(n2)。
转载请注明原文地址:https://kaotiyun.com/show/fRWZ777K
本试题收录于： 嵌入式系统设计师上午基础知识考试题库软考中级分类
0

嵌入式系统设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)