求解两个长度为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
解析
蛮力法，对X每一个子序列，判断是否也是Y子序列，其中，长度为n序列X共有2^n个子序列，判断其是否是Y子序列时间是n，因此是n*2^n；采用动态规划法自底向上实现时，根据递归公式，实际是关于i和j两重循环，因此时间复杂度是n^2.
你可能感兴趣的试题
-
- A.V(S2)和P(S4)
- B.P(S2)和V(S4)
- C.P(S2)和P(S4)
- D.V(S2)和V(S4)
- 查看答案
-
- A.V（S1）P（S2）和V（S3）
- B.P（S1）V（S2）和V（S3）
- C.V（S1）V（S2）和V（S3）
- D.P（S1）P（S2）和V（S3）
- 查看答案
-
- A.P（S4）和V（S4）V（S5）
- B.V（S5）和P（S4）P（S5）
- C.V（S3）和V（S4）V（S5）
- D.P（S3）和P（S4）V（P5）
- 查看答案
-
- A.P(S3)和V(S4)V(S5)
- B.V(S3)和P(S4)P(S5)
- C.P(S3)和P(S4)P(S5)
- D.V(S3)和V(S4)V(S5)
- 查看答案
-
- A.P（S2）和P（S4）
- B.P（S2）和V（S4）
- C.V（S2）和P（S4）
- D.V（S2）和V（S4）
- 查看答案