| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 |
| 数据结构:绪论 [2025/12/11 16:21] – [2. 分治法 (Divide and Conquer)] 张叶安 | 数据结构:绪论 [2025/12/11 16:24] (当前版本) – [1. 穷举法 (Brute Force)] 张叶安 |
|---|
| ==== 1. 穷举法 (Brute Force) ==== | ==== 1. 穷举法 (Brute Force) ==== |
| |
| * **别名**：暴力破解法。 | * **别名**：暴力破解法。 |
| * **核心**：列出所有可能的情况，逐一验证。 | * **核心**：列出所有可能的情况，逐一验证。 |
| * **优点**：逻辑简单，几乎适用于所有问题，保证能找到解（如果存在）。 | * **优点**：逻辑简单，几乎适用于所有问题，保证能找到解（如果存在）。 |
| * **缺点**：效率极低。 | * **缺点**：效率极低。 |
| * **案例**：破解4位数字密码。从 `0000` 试到 `9999`，最多试 10000 次。 | * **案例**：破解4位数字密码。从 `0000` 试到 `9999`，最多试 10000 次。 |
| |
| ==== 2. 分治法 (Divide and Conquer) ==== | ==== 2. 分治法 (Divide and Conquer) ==== |
| ==== 3. 动态规划 (Dynamic Programming, DP) ==== | ==== 3. 动态规划 (Dynamic Programming, DP) ==== |
| |
| * **核心**：**历史记录**。通过空间换时间。 | * **核心**：**历史记录**。通过空间换时间。 |
| * **原理**：将复杂问题分解为子问题，但与分治法不同的是，DP 的子问题是**重叠**的。为了避免重复计算，DP 会把每个子问题的结果**存进一张表**里。 | * **原理**：将复杂问题分解为子问题，但与分治法不同的是，DP 的子问题是**重叠**的。为了避免重复计算，DP 会把每个子问题的结果**存进一张表**里。 |
| * **案例：斐波那契数列** (1, 1, 2, 3, 5, 8...) | * **案例：斐波那契数列** (1, 1, 2, 3, 5, 8...) |
| * 求第 5 个数：$F(5) = F(4) + F(3)$ | * 求第 5 个数：$F(5) = F(4) + F(3)$ |
| * 求 $F(4)$ 时需要算 $F(3) + F(2)$。 | * 求 $F(4)$ 时需要算 $F(3) + F(2)$。 |
| ==== 4. 贪心算法 (Greedy) ==== | ==== 4. 贪心算法 (Greedy) ==== |
| |
| * **核心**：**活在当下**。 | * **核心**：**活在当下**。 |
| * **策略**：每一步都做出在当前看来最好的选择。它不从整体最优考虑，但在很多情况下（如最小生成树），局部最优能导致全局最优。 | * **策略**：每一步都做出在当前看来最好的选择。它不从整体最优考虑，但在很多情况下（如最小生成树），局部最优能导致全局最优。 |
| * **案例：找零钱** | * **案例：找零钱** |
| * 问题：找 66 元，纸币规格有 100, 50, 20, 10, 5, 1。 | * 问题：找 66 元，纸币规格有 100, 50, 20, 10, 5, 1。 |
| * 贪心策略：优先用面值最大的。 | * 贪心策略：优先用面值最大的。 |
| * 步骤： | * 步骤： |
| 1. 66 < 100，跳过。 | * 66 < 100，跳过。 |
| 2. 66 >= 50，**给一张 50**。剩 16。 | * 66 >= 50，**给一张 50**。剩 16。 |
| 3. 16 < 20，跳过。 | * 16 < 20，跳过。 |
| 4. 16 >= 10，**给一张 10**。剩 6。 | * 16 >= 10，**给一张 10**。剩 6。 |
| 5. 6 >= 5，**给一张 5**。剩 1。 | * 6 >= 5，**给一张 5**。剩 1。 |
| 6. **给一张 1**。结束。 | * **给一张 1**。结束。 |
| * **局限**：如果纸币规格是 1, 3, 4，找 6 元。贪心会给 4+1+1 (3张)，但最优解是 3+3 (2张)。此时贪心失效，需用 DP。 | * **局限**：如果纸币规格是 1, 3, 4，找 6 元。贪心会给 4+1+1 (3张)，但最优解是 3+3 (2张)。此时贪心失效，需用 DP。 |
| |
| ==== 5. 回溯法 (Backtracking) ==== | ==== 5. 回溯法 (Backtracking) ==== |
| |
| * **核心**：**试错与回退**。 | * **核心**：**试错与回退**。 |
| * **策略**：这是一种深度优先搜索 (DFS)。一条路走到黑，如果发现走不通（不满足条件），就**回溯**到上一个路口，换一条路继续走。 | * **策略**：这是一种深度优先搜索 (DFS)。一条路走到黑，如果发现走不通（不满足条件），就**回溯**到上一个路口，换一条路继续走。 |
| * **剪枝 (Pruning)**：在搜索过程中，如果发现当前分支已经不可能找到解，就直接切断该分支，不再往下搜，大大提高效率。 | * **剪枝 (Pruning)**：在搜索过程中，如果发现当前分支已经不可能找到解，就直接切断该分支，不再往下搜，大大提高效率。 |
| * **典型应用**：走迷宫、八皇后问题、数独。 | * **典型应用**：走迷宫、八皇后问题、数独。 |
| |
| <html> | <html> |
张叶安