最长公共子序列复杂度

最长公共子序列（LCS）问题是指：给定两个序列，找出它们最长的公共子序列。其时间复杂度为 $O(mn)$，其中 $m$ 和 $n$ 分别是两个序列的长度。LCS 问题可以用动态规划算法来解决，具体实现时需要用到一个二维数组来记录中间结果。对于序列 $A$ 和 $B$，令 $C[i][j]$ 表示 $A[1...i]$ 和 $B[1...j]$ 的最长公共子序列长度，则有以下递推式：

$$
C[i][j] =
\begin{cases}
0, & \text{if } i = 0 \text{ or } j = 0 \\
C[i-1] + 1, & \text{if } i > 0 \text{ and } j > 0 \text{ and } A[i] = B[j] \\
\max(C[i][j-1], C[i-1][j]), & \text{if } i > 0 \text{ and } j > 0 \text{ and } A[i] \neq B[j]
\end{cases}
$$

最终的 LCS 长度即为 $C[m][n]$。

相关问题

最长公共子序列的复杂度

最长公共子序列（Longest Common Subsequence, LCS）是指两个序列中最长的那个相同的子序列。计算两个字符串的LCS通常使用动态规划算法。经典的动态规划解决方案，如Hunt–Szymanski算法或Kasai算法，时间复杂度是O(n*m)，其中n和m分别是输入字符串的长度。

这个复杂度基于一个二维数组，每一格代表两个字符对应位置是否在共同子序列中，以及当前为止已经找到的最长公共子序列长度。随着遍历两个字符串的每个字符，算法填充并更新这个数组，所以空间复杂度也是O(n*m)。

然而，如果采用空间优化的版本，比如只保存行（或列）状态，称为“滚动数组”或“自底向上”的策略，空间复杂度可以降低到O(min(n, m))，但仍保持O(n*m)的时间复杂度。

最长公共子序列时间复杂度

最长公共子序列（Longest Common Subsequence, LCS）是一个经典的计算机科学问题，通常用于比较两个序列的相似性。动态规划算法是解决这个问题的主要方法，其基本思想是通过构建一个二维数组来存储前缀子序列的长度。

时间复杂度分析：
经典的动态规划算法，如Hunt-Szymanski算法或Floyd-Warshall的扩展版本，使用一个二维数组，其中每个元素表示两个输入序列从起始到当前位置的最长公共子序列长度。数组大小是输入序列长度的平方，即O(n^2)，其中n是序列的长度。

- 动态规划填充过程：需要填充整个数组，所以每一行和每一列的遍历都是一次O(n)操作，总共有n行和n列，所以时间复杂度是O(n^2)。
- 查找结果：找到最终最长公共子序列的长度或实际子序列的过程是线性的，即O(n)。

因此，最长公共子序列问题的总时间复杂度是O(n^2)，这是在最坏情况下的表现，即输入序列完全不相似。如果序列部分相似，可以设计一些优化来减少计算量，但主要的时间消耗仍集中在动态规划矩阵上。