算法分类
CIE A-Level 计算机科学· 第9单元：算法设计与问题求解· 15 分钟阅读
1. 蛮力算法★★☆☆☆⏱ 4 min
蛮力法是最简单的算法分类，它不使用更优化的方法，而是依赖检查每一种可能的解。
蛮力算法
蛮力算法会生成并检查问题的每一个可能候选解，只要解存在就一定能找到所有有效解。
例:
尝试所有3位数字组合打开挂锁。
一个有10名学生的班级需要找出所有生日相同的学生对。该问题的蛮力方法属于哪类算法？
- 1
- 计算总共有多少对学生：，数量很小，易于处理。
- 2
- 生成群体中所有可能的学生对。
- 3
- 检查每对学生的生日是否相同。
- 4
- 由于该方法检查了所有可能的学生对（即所有可能候选解），符合蛮力法的定义。
Exam tip:
考试中你必须说明蛮力法会检查所有可能解，才能拿到解释分。
2. 分治算法与贪心算法★★★☆☆⏱ 5 min
分治和贪心是两种最常见的优化算法分类，都用于解决蛮力法求解速度过慢的大规模问题。
分治
分治反复将大问题拆分为多个同类型的较小独立子问题，递归求解每个子问题后合并结果，最终得到原问题的解。
例:
二分查找、归并排序。
贪心算法
贪心算法在问题的每一步都做出局部最优选择（当前步骤下的最优选择），不会为未来步骤提前规划。
例:
Dijkstra最短路径算法、最小生成树算法。
自动售货机使用尽可能少的硬币找零，每次总是选择符合剩余找零额的最大面额硬币。该方法属于哪类算法？
- 1
- 每一步算法都为当前剩余金额选择最优硬币（最大面额）。
- 2
- 它不会检查所有硬币组合来找到全局最优解，仅在每一步做出最优局部选择。
- 3
- 这符合贪心算法的核心定义，因此分类为贪心算法。
3. 动态规划与回溯法★★★★☆⏱ 6 min
动态规划和回溯法用于需要探索或重用部分解的更复杂问题。
动态规划
动态规划通过存储已求解子问题的结果来避免重复计算，可求解具有重叠子问题和最优子结构的问题。
例:
计算斐波那契数、最长公共子序列。
回溯法
回溯法增量式构造解，一旦确定某个部分解无法得到有效完整解，就会放弃（剪枝）该部分解。
例:
解数独、N皇后问题。
解9×9数独时，某算法先在空格填入一个数字，检查是否有效，再移动到下一个空格。如果卡住了，就撤销上一步填入的数字，尝试下一个可能值。该算法属于哪类？
- 1
- 算法每次构造一个格子的解（增量式构造）。
- 2
- 如果某个部分解无效（卡住，下一个格子没有可用的有效数字），就放弃该部分解，回溯到之前的步骤尝试其他值。
- 3
- 这符合回溯法的核心定义，因此是正确分类。
4. 解答考试题目★★★☆☆⏱ 4 min
测试你的理解：
快速排序围绕基准点拆分数组，对每个子数组排序后合并结果，它属于哪类算法？
蛮力法
分治
贪心
动态规划
显示答案
分治 —正确！快速排序是经典的分治算法。
通过存储每个先前结果而非重新计算来求第20个斐波那契数，该方法属于哪类算法？
回溯法
贪心
蛮力法
动态规划
显示答案
动态规划 —正确！存储重叠子问题的结果是动态规划的核心。
5. 常见陷阱
错误做法:
将所有递归算法都归为分治
原因:
不是所有递归算法都会将问题拆分为独立子问题，多种分类的算法都可以使用递归。
正确做法:
归为分治之前，确认问题被拆分为独立子问题，且最终需要合并子问题结果。
错误做法:
因为算法找不到最优解就不将其归为贪心
原因:
分类依据是求解思路而非结果。即使贪心方法不能保证得到全局最优解，它仍然属于贪心分类。
正确做法:
无论最终结果如何，都根据求解思路（每一步选择局部最优）进行分类。
错误做法:
混淆动态规划和分治
原因:
两者都会将问题拆分为子问题，但分治仅适用于不重叠的子问题。
正确做法:
如果子问题重复出现，且存储结果避免重复计算，则属于动态规划。
错误做法:
混淆回溯法和蛮力法
原因:
蛮力法检查所有可能解，而回溯法提前剪去无效部分解，仅需要检查少得多的候选解。
正确做法:
如果算法提前放弃无效部分解，则属于回溯法，而非蛮力法。
错误做法:
题目要求解释时仅写出分类
原因:
2分题中，分类占1分，支撑解释占1分。
正确做法:
当题目要求解释时，一定要补充一句话，将算法的求解思路和该分类的核心特征关联起来。
6. 速查表
算法分类 | 核心特征 | 常见例子 |
|---|---|---|
蛮力法 | 检查所有可能解 | PIN破解 |
分治 | 拆分为独立子问题 | 二分查找、归并排序 |
贪心 | 每一步选择局部最优 | 找零问题、Dijkstra算法 |
动态规划 | 存储重叠子问题结果 | 斐波那契数、最长公共子序列 |
回溯法 | 提前剪去无效部分解 | 数独、N皇后问题 |
7. 常见问题
算法分类题目通常占多少分？
大多数为1-2分：正确分类得1分，说明符合该分类的理由得1分。
真题中的出现
AI 根据考纲规律估算的考点位置,请对照官方真题核实准确性。仅作复习重点参考。
- 2022 · 2
识别算法分类
- 2023 · 2
解释算法类型的选择依据
深入阅读
下一步
算法分类是CIE 9618中算法设计与分析所有后续内容的核心基础。它帮助你为新问题选择合适的求解思路，理解为什么同一问题会使用不同算法，并解答卷二中频繁出现的分类题目。清晰掌握每种分类的特征也能为你学习时间复杂度分析等内容做好准备，该主题需要你比较同一问题不同思路的效率。你可以学习以下主题来巩固延伸现有知识。