2. 从业资格
  3. 求解两个长度为n的序列X和Y的一个最长公共子序列（如序列ABCBDAB和BDCA

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

考试题库2022-08-02  85
问题 求解两个长度为n的序列X和Y的一个最长公共子序列（如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA）可以采用多种计算方法。如可以采用蛮力法，对X的每一个子序列，判断其是否也是Y的子序列，最后求出最长的即可，该方法的时间复杂度为（请作答此空）。经分析发现该问题具有最优子结构，可以定义序列长度分别为i和j的两个序列X和Y的最长公共子序列的长度为c[i,j]，如下式所示。采用自底向上的方法实现该算法，则时间复杂度为（ ）A.O（n^2）B.O（n^21gn）C.O（n^3）D.O（n2^n）
选项 A.O（n^2）
B.O（n^21gn）
C.O（n^3）
D.O（n2^n）
答案 D
解析 蛮力法，对X的每一个子序列，判断是否也是Y的子序列，其中，长度为n的序列X共有2^n个子序列，判断其是否是Y的子序列时间是n，因此是n*2^n；采用动态规划法自底向上实现时，根据递归公式，实际是关于i和j的两重循环，因此时间复杂度是n^2.
转载请注明原文地址:https://tihaiku.com/congyezige/2424436.html
本试题收录于： 中级 嵌入式系统设计师题库软件水平考试初中高级分类

中级 嵌入式系统设计师

软件水平考试初中高级

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