已知序列X={x1,x2,…,xm},序列Y={y1,y2,…,yn},使用动态规划算法求解序列X和Y的最长公共子序列,其最坏时间复杂度为(
)。
A: O(m * n)
B: O(m + n)
C: O(m
* 2n)
D: O(n
* 2m)
)。
A: O(m * n)
B: O(m + n)
C: O(m
* 2n)
D: O(n
* 2m)
举一反三
- 给定2个序列X={x1,x2,...,xm}和Y={y1,y2,...,yn},找出X和Y的最长公共子序列。使用穷举法时,对X的所有子列,检查它是否也是Y的子序列,从而确定它是否为X和Y的公共子序列。那么Y有多少个不同子序列 A: m B: 2 C: n D: 2
- 使用动态规划算法求两条长度分别为m和n的序列的最长公共子序列，其时间复杂度为()。 A: O(n^2) B: O(n*m) C: O(nlogm) D: O(m^n)
- 使用动态规划算法求解最长公共子序列问题的时间复杂度为()。【m和n分别为两条序列的长度】 A: O(m+n) B: O(m*n) C: O(mlogn) D: O(m^n)
- 求时间复杂度：x=n; //n>1y=0;while(x≥(y+1)* (y+1)){ y++;} A: O(1) B: O(n) C: O(√n ) D: O(n^2)
- 使用动态规划算法求解最长公共子序列问题，引入数组c[i][j]存储序列x[1..i]和y[1..j]的最长公共子序列的长度，则对于长度为m和n的两条序列，其最长公共子序列的长度为c[m][n]。