# 算法分类

> CIE A-Level 计算机科学 · 9618
> 来源: https://www.owlsprep.com/zh/study/cie-9618-u9-algorithm-classification/

本模块讲解问题求解中算法的主要分类、各类算法的核心特征，以及如何在CIE 9618考试题目中正确识别算法类型。

**先修:** [算法设计基础入门](https://www.owlsprep.com/zh/study/cie-9618-u9-algorithm-design-fundamentals/)

## 学习目标

- 根据算法的问题求解思路对其分类
- 区分不同算法类型的核心特征
- 为给定问题场景确定正确的算法分类
- 符合CIE评分标准要求作答算法分类题目

## 蛮力算法

蛮力法是最简单的算法分类，它不使用更优化的方法，而是依赖检查每一种可能的解。

**蛮力算法** — 蛮力算法会生成并检查问题的每一个可能候选解，只要解存在就一定能找到所有有效解。

*例:* 尝试所有3位数字组合打开挂锁。

**例题:** 一个有10名学生的班级需要找出所有生日相同的学生对。该问题的蛮力方法属于哪类算法？

1. 1. 计算总共有多少对学生：$C(10,2) = 45$，数量很小，易于处理。
2. 2. 生成群体中所有可能的学生对。
3. 3. 检查每对学生的生日是否相同。
4. 4. 由于该方法检查了所有可能的学生对（即所有可能候选解），符合蛮力法的定义。

> **考试提示:** 考试中你必须说明蛮力法会检查所有可能解，才能拿到解释分。

## 分治算法与贪心算法

分治和贪心是两种最常见的优化算法分类，都用于解决蛮力法求解速度过慢的大规模问题。

**分治** — 分治反复将大问题拆分为多个同类型的较小独立子问题，递归求解每个子问题后合并结果，最终得到原问题的解。

*例:* 二分查找、归并排序。

**贪心算法** — 贪心算法在问题的每一步都做出局部最优选择（当前步骤下的最优选择），不会为未来步骤提前规划。

*例:* Dijkstra最短路径算法、最小生成树算法。

**例题:** 自动售货机使用尽可能少的硬币找零，每次总是选择符合剩余找零额的最大面额硬币。该方法属于哪类算法？

1. 1. 每一步算法都为当前剩余金额选择最优硬币（最大面额）。
2. 2. 它不会检查所有硬币组合来找到全局最优解，仅在每一步做出最优局部选择。
3. 3. 这符合贪心算法的核心定义，因此分类为贪心算法。

## 动态规划与回溯法

动态规划和回溯法用于需要探索或重用部分解的更复杂问题。

**动态规划** — 动态规划通过存储已求解子问题的结果来避免重复计算，可求解具有重叠子问题和最优子结构的问题。

*例:* 计算斐波那契数、最长公共子序列。

**回溯法** — 回溯法增量式构造解，一旦确定某个部分解无法得到有效完整解，就会放弃（剪枝）该部分解。

*例:* 解数独、N皇后问题。

**例题:** 解9×9数独时，某算法先在空格填入一个数字，检查是否有效，再移动到下一个空格。如果卡住了，就撤销上一步填入的数字，尝试下一个可能值。该算法属于哪类？

1. 1. 算法每次构造一个格子的解（增量式构造）。
2. 2. 如果某个部分解无效（卡住，下一个格子没有可用的有效数字），就放弃该部分解，回溯到之前的步骤尝试其他值。
3. 3. 这符合回溯法的核心定义，因此是正确分类。

## 解答考试题目

**考试命令词**

CIE 9618在算法分类题目中使用统一的指令术语：

- **State the classification** — 仅需写出算法类型，无需解释，该题占1分 *(State the classification of binary search (1 mark))*

- **Explain your answer** — 给出该分类符合题目所给问题的一个核心特征，额外占1分 *(Explain why binary search fits your classification (2 marks))*

**概念自测**

测试你的理解：

1. 快速排序围绕基准点拆分数组，对每个子数组排序后合并结果，它属于哪类算法？

   - 蛮力法
   - 分治
   - 贪心
   - 动态规划

   *解析:* 正确！快速排序是经典的分治算法。

2. 通过存储每个先前结果而非重新计算来求第20个斐波那契数，该方法属于哪类算法？

   - 回溯法
   - 贪心
   - 蛮力法
   - 动态规划

   *解析:* 正确！存储重叠子问题的结果是动态规划的核心。

## 常见错误

- **错误做法:** 将所有递归算法都归为分治
  - 原因: 不是所有递归算法都会将问题拆分为独立子问题，多种分类的算法都可以使用递归。
  - 正确做法: 归为分治之前，确认问题被拆分为独立子问题，且最终需要合并子问题结果。
- **错误做法:** 因为算法找不到最优解就不将其归为贪心
  - 原因: 分类依据是求解思路而非结果。即使贪心方法不能保证得到全局最优解，它仍然属于贪心分类。
  - 正确做法: 无论最终结果如何，都根据求解思路（每一步选择局部最优）进行分类。
- **错误做法:** 混淆动态规划和分治
  - 原因: 两者都会将问题拆分为子问题，但分治仅适用于不重叠的子问题。
  - 正确做法: 如果子问题重复出现，且存储结果避免重复计算，则属于动态规划。
- **错误做法:** 混淆回溯法和蛮力法
  - 原因: 蛮力法检查所有可能解，而回溯法提前剪去无效部分解，仅需要检查少得多的候选解。
  - 正确做法: 如果算法提前放弃无效部分解，则属于回溯法，而非蛮力法。
- **错误做法:** 题目要求解释时仅写出分类
  - 原因: 2分题中，分类占1分，支撑解释占1分。
  - 正确做法: 当题目要求解释时，一定要补充一句话，将算法的求解思路和该分类的核心特征关联起来。

## 速查表

| 算法分类 | 核心特征 | 常见例子 |
| --- | --- | --- |
| 蛮力法 | 检查所有可能解 | PIN破解 |
| 分治 | 拆分为独立子问题 | 二分查找、归并排序 |
| 贪心 | 每一步选择局部最优 | 找零问题、Dijkstra算法 |
| 动态规划 | 存储重叠子问题结果 | 斐波那契数、最长公共子序列 |
| 回溯法 | 提前剪去无效部分解 | 数独、N皇后问题 |

## 下一步

算法分类是CIE 9618中算法设计与分析所有后续内容的核心基础。它帮助你为新问题选择合适的求解思路，理解为什么同一问题会使用不同算法，并解答卷二中频繁出现的分类题目。清晰掌握每种分类的特征也能为你学习时间复杂度分析等内容做好准备，该主题需要你比较同一问题不同思路的效率。你可以学习以下主题来巩固延伸现有知识。

- [标准查找算法](https://www.owlsprep.com/zh/study/cie-9618-u9-standard-searching-algorithms/)
- [标准排序算法](https://www.owlsprep.com/zh/study/cie-9618-u9-standard-sorting-algorithms/)
- [算法跟踪](https://www.owlsprep.com/zh/study/cie-9618-u9-algorithm-tracing/)

---

来自 [OwlsPrep](https://www.owlsprep.com) —— A-Level / IB / AP / IGCSE 免费学习指南，依据官方考纲编写。原页面：https://www.owlsprep.com/zh/study/cie-9618-u9-algorithm-classification/