给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。它的时间复杂度是多少

最长公共子序列问题可以使用动态规划来解决。设L[i][j]表示X的前i个字符和Y的前j个字符的最长公共子序列的长度，则有以下递推式：

L[i][j] = 0, if i = 0 or j = 0
L[i-1][j-1] + 1, if xi = yj
max(L[i-1][j], L[i][j-1]), otherwise

其中，第一行和第一列表示空序列和任何序列的最长公共子序列长度都为0。如果X和Y的第i个和第j个字符相同，那么它们一定是最长公共子序列的一部分，所以L[i][j]的值为L[i-1][j-1]加1。如果不相同，那么最长公共子序列一定不包括xi或yj，所以L[i][j]的值为L[i-1][j]和L[i][j-1]中的最大值。

最终的最长公共子序列的长度就是L[m][n]。要找出具体的最长公共子序列，可以从L[m][n]开始，根据递推式倒推回去，直到i=0或j=0为止，每次选择L[i-1][j-1]+1或L[i-1][j]或L[i][j-1]中的最大值所对应的操作，即可得到最长公共子序列。具体实现可以参考代码。

时间复杂度为O(mn)，其中m和n分别是X和Y的长度。