14.7 算法基础章节回顾

本章回顾要把知识压缩成可用于做题的“判断链”。算法题的失分点往往不是完全不会，而是忽略了题干里的限定词：有序、顺序存储、最坏情况、稳定、基本有序、辅助空间、关键字范围。

一页式总表

模块	必会结论	典型陷阱
算法特性	有穷、确定、可行、输入、输出	输入可以没有，输出至少一个
时间复杂度	看最高阶增长	不要把常数和低阶项带进大 $O$
空间复杂度	看辅助空间	输入数组本身不是辅助空间
分治	子问题独立，最后合并	与动态规划混淆
贪心	局部最优选择	不是所有最优化问题都能贪心
动态规划	重叠子问题、查表	辅助数组是空间复杂度来源
回溯	试探、失败、撤销	本质是搜索解空间
二分查找	有序顺序表，$O(\log n)$	mid 比较后不能重复进入新区间
哈希查找	散列函数 + 冲突处理	线性探测要循环找下一个空位
排序	复杂度、空间、稳定性、场景	快排平均好但最坏差；归并稳定但费空间

最容易混淆的概念

分治、动态规划、贪心

对比	分治	动态规划	贪心
子问题关系	通常相互独立	大量重叠	不系统求所有子问题
是否保存中间结果	通常不强调	强调表格/数组记录	通常不保存完整状态表
选择是否回头	合并子问题结果	根据状态转移求最优	选择后一般不回头
典型例子	归并排序	矩阵连乘、0-1 背包	活动选择、部分背包

堆排序、快速排序、归并排序

算法	都是 $O(n\log n)$ 吗	稳定吗	空间特点	一句话区分
堆排序	最好/平均/最坏都是	不稳定	$O(1)$	空间省，过程依赖堆
快速排序	平均是，最坏不是	不稳定	递归栈	平均快，但枢轴差会退化
归并排序	最好/平均/最坏都是	稳定	$O(n)$	稳定可靠，但需要辅助数组

顺序查找、二分查找、哈希查找

查找	要不要有序	存储限制	速度直觉
顺序查找	不需要	顺序/链式都可	逐个找，慢但通用
二分查找	必须有序	顺序存储更合适	每次砍半
哈希查找	不靠有序	依赖散列表	理想很快，冲突会影响

复杂度题的做法

1. 找基本操作：通常是循环体中的比较、赋值、递归调用。
2. 看循环层数和循环变量变化：i++ 多为线性，i*=2 多为对数。
3. 递归看分解规模：如 $T(n)=2T(n/2)+n$ 是归并类结构。
4. 最后只保留最高阶。

常见阶序从小到大：

$$O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(n^3)<O(2^n)<O(n!)$$

排序题的“条件优先”表

题干关键词	首先想到
基本有序	直接插入排序
相等关键字相对顺序	稳定性
稳定且 $O(n\log n)$	归并排序
最坏 $O(n\log n)$ 且 $O(1)$ 空间	堆排序
平均运行时间优秀	快速排序
大顶堆、小顶堆	堆排序
分配、收集、十进制位	基数排序
关键字范围 0 到 9	计数/基数思想

考前训练清单

• 手算两个循环的时间复杂度。
• 写出二分查找三次边界变化。
• 用线性探测构造一个哈希表。
• 判断一个数组按层序表示后是否为大顶堆。
• 解释为什么简单选择排序不稳定。
• 对两个有序表做一次归并并统计比较次数。
• 区分 0-1 背包适合动态规划，部分背包可用贪心。

单选

稳定且需要 $O(n)$ 辅助空间的常见排序算法是哪一个？

A归并排序B堆排序C快速排序D希尔排序

单选

如果一个最优化问题存在大量重叠子问题，需要把中间结果保存在表中反复查用，通常采用哪种算法策略？

A分治法B贪心法C动态规划法D回溯法

本章收束

算法基础的核心能力是“看条件选方法”。复杂度题看增长，策略题看问题结构，查找题看数据条件，排序题看稳定性、空间和初始状态。把这些前提读清楚，本章大多数选择题都能用排除法稳定拿分。