97 lines
3.8 KiB
Markdown
97 lines
3.8 KiB
Markdown
|
以下是**最长公共子序列（LCS）**和**最小编辑距离**两个算法的基本思想、分析和时间复杂度计算：
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
### **1. 最长公共子序列（LCS）**
|
|||
|
|
|
|||
|
|
#### **基本思想**
|
|||
|
|
最长公共子序列（LCS）的核心是通过动态规划构建一个二维表，记录两个字符串在不同前缀长度下的公共子序列的最大长度。
|
|||
|
|
|
|||
|
|
- 定义状态：
|
|||
|
|
设 \( dp[i][j] \) 表示字符串 \( X[0:i] \) 和 \( Y[0:j] \) 的最长公共子序列长度。
|
|||
|
|
|
|||
|
|
- 状态转移方程：
|
|||
|
|
- 如果 \( X[i-1] == Y[j-1] \)：说明当前字符可以纳入公共子序列：
|
|||
|
|
\[
|
|||
|
|
dp[i][j] = dp[i-1][j-1] + 1
|
|||
|
|
\]
|
|||
|
|
- 如果 \( X[i-1] \neq Y[j-1] \)：说明当前字符不匹配，取之前子问题的最大值：
|
|||
|
|
\[
|
|||
|
|
dp[i][j] = \max(dp[i-1][j], dp[i][j-1])
|
|||
|
|
\]
|
|||
|
|
|
|||
|
|
- 初始条件：
|
|||
|
|
\( dp[i][0] = 0 \) 和 \( dp[0][j] = 0 \)，表示任意一个字符串和空串的最长公共子序列长度为 0。
|
|||
|
|
|
|||
|
|
- 最终结果：
|
|||
|
|
\( dp[m][n] \) 表示 \( X \) 和 \( Y \) 的最长公共子序列长度，其中 \( m, n \) 分别为 \( X \) 和 \( Y \) 的长度。
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
#### **算法分析**
|
|||
|
|
- **时间复杂度：**
|
|||
|
|
构造 \( dp \) 表需要遍历 \( m \times n \) 的网格，其中 \( m \) 和 \( n \) 是两个字符串的长度。因此时间复杂度为 \( O(m \times n) \)。
|
|||
|
|
|
|||
|
|
- **空间复杂度：**
|
|||
|
|
二维表 \( dp \) 的空间复杂度为 \( O(m \times n) \)。若只需要结果，可以优化为一维数组，降低到 \( O(\min(m, n)) \)。
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
### **2. 最小编辑距离**
|
|||
|
|
|
|||
|
|
#### **基本思想**
|
|||
|
|
最小编辑距离的目的是计算将字符串 \( A \) 转换为字符串 \( B \) 的最小操作次数（插入、删除、替换）。同样使用动态规划构建一个二维表解决。
|
|||
|
|
|
|||
|
|
- 定义状态：
|
|||
|
|
\( dp[i][j] \) 表示将 \( A[0:i] \) 转换为 \( B[0:j] \) 的最小操作次数。
|
|||
|
|
|
|||
|
|
- 状态转移方程：
|
|||
|
|
- 如果 \( A[i-1] == B[j-1] \)：当前字符无需修改：
|
|||
|
|
\[
|
|||
|
|
dp[i][j] = dp[i-1][j-1]
|
|||
|
|
\]
|
|||
|
|
- 如果 \( A[i-1] \neq B[j-1] \)：需要考虑三种操作：
|
|||
|
|
1. **插入**：将 \( B[j-1] \) 插入到 \( A[0:i] \) 的末尾：
|
|||
|
|
\[
|
|||
|
|
dp[i][j] = dp[i][j-1] + 1
|
|||
|
|
\]
|
|||
|
|
2. **删除**：删除 \( A[i-1] \)：
|
|||
|
|
\[
|
|||
|
|
dp[i][j] = dp[i-1][j] + 1
|
|||
|
|
\]
|
|||
|
|
3. **替换**：将 \( A[i-1] \) 替换为 \( B[j-1] \)：
|
|||
|
|
\[
|
|||
|
|
dp[i][j] = dp[i-1][j-1] + 1
|
|||
|
|
\]
|
|||
|
|
取三种操作的最小值：
|
|||
|
|
\[
|
|||
|
|
dp[i][j] = \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
|
|||
|
|
\]
|
|||
|
|
|
|||
|
|
- 初始条件：
|
|||
|
|
\( dp[i][0] = i \) 表示将 \( A[0:i] \) 转换为空串需要删除 \( i \) 次，
|
|||
|
|
\( dp[0][j] = j \) 表示将空串转换为 \( B[0:j] \) 需要插入 \( j \) 次。
|
|||
|
|
|
|||
|
|
- 最终结果：
|
|||
|
|
\( dp[m][n] \) 表示从 \( A \) 转换为 \( B \) 的最小编辑距离，其中 \( m, n \) 分别为 \( A \) 和 \( B \) 的长度。
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
#### **算法分析**
|
|||
|
|
- **时间复杂度：**
|
|||
|
|
与 LCS 相同，需要构造一个 \( m \times n \) 的动态规划表，时间复杂度为 \( O(m \times n) \)。
|
|||
|
|
|
|||
|
|
- **空间复杂度：**
|
|||
|
|
二维表的空间复杂度为 \( O(m \times n) \)。通过滚动数组优化，可以降低到 \( O(\min(m, n)) \)。
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
### **对比总结**
|
|||
|
|
| **算法** | **时间复杂度** | **空间复杂度** | **核心思想** |
|
|||
|
|
|-------------------|----------------|----------------|--------------------------------------|
|
|||
|
|
| 最长公共子序列 | \( O(m \times n) \) | \( O(m \times n) \) | 构建二维表，利用匹配与不匹配分治求解 |
|
|||
|
|
| 最小编辑距离 | \( O(m \times n) \) | \( O(m \times n) \) | 通过插入、删除、替换操作递归求解 |
|
|||
|
|
|
|||
|
|
这两个算法均使用动态规划解决，思想和实现类似，但问题背景不同：
|
|||
|
|
- LCS 关注的是**匹配**字符的最大子序列长度。
|
|||
|
|
- 最小编辑距离则是计算**最少操作次数**。
|