第14章 算法基础
算法基础承接数据结构：数据结构决定数据怎么组织，算法决定如何求解问题。软考里这一章既考上午选择题，也影响下午算法应用题，重点不是背术语，而是能判断复杂度、识别算法策略、模拟查找排序过程。
本章学习地图
| 模块 | 页面 | 核心能力 |
|---|---|---|
| 算法与复杂度 | 算法的特性、复杂度概述、时间复杂度01、时间复杂度02 | 会看基本操作、增长阶、辅助空间 |
| 算法策略 | 策略概述、策略识别、分治法、贪心法、动态规划法、回溯法 | 会根据题干关键词判断策略 |
| 查找算法 | 查找概述、顺序查找、二分查找、哈希散列表 | 会比较前提、过程和效率 |
| 排序算法 | 排序概述、基本概念、插入类排序、选择类排序、归并排序、基数排序、排序对比 | 会记复杂度、稳定性、适用场景 |
学算法的四个层次
| 层次 | 你要能回答 |
|---|---|
| 表达 | 算法可以用自然语言、流程图、伪代码、C 语言表示 |
| 评价 | 时间复杂度和空间复杂度怎么看 |
| 策略 | 问题是分治、贪心、动态规划还是回溯 |
| 过程 | 查找和排序每一步如何变化 |
本章最高频的判断线索
| 关键词/结构 | 优先想到 |
|---|---|
| “折半”“二分”“分成两个子问题” | 分治、二分查找 |
| “当前最优”“每次选择最小/最大” | 贪心 |
| “最优子结构”“递推式”“填表” | 动态规划 |
| “尝试、撤销、所有可能、解空间树” | 回溯 |
| “有序表” | 二分查找 |
| “散列函数、冲突” | 哈希表 |
| “稳定性、趟数、比较次数” | 排序算法 |
复习建议
- 复杂度题先抓最大增长项，不被常数和低阶项带跑。
- 空间复杂度只看辅助空间，不把输入数组本身算进去。
- 策略题不要只看“最优”，贪心和动态规划都可能求最优，要看是否填表、是否全局可由局部最优保证。
- 排序题必须同时记时间、空间、稳定性，否则选择题容易被干扰项拆开。