Appearance
算法和算法评价
核心思想
算法的基本概念
算法（Algorithm）是对特定问题求解步骤的描述，是一个有穷的指令序列。
算法的五个特性：
| 特性 | 含义 |
|---|---|
| 有穷性 | 必须在有限步后结束，每一步都在有限时间内完成 |
| 确定性 | 每条指令含义明确，相同输入只能产生相同输出 |
| 可行性 | 所有操作都可通过已实现的基本运算有限次执行来完成 |
| 输入 | 有零个或多个输入 |
| 输出 | 至少有一个输出 |
注意"有穷性"和"确定性"的区别：有穷性强调的是"会停下来"，确定性强调的是"不会有歧义"。
一个好的算法还应该考虑：正确性、可读性、健壮性、高效率与低存储量需求。
算法效率的度量
时间复杂度
事后统计法受硬件和数据影响太大，实际中使用事前分析法——统计算法中基本操作的执行次数 T(n) 作为时间度量。
大 O 记号：T(n) = O(f(n)) 表示存在常数 C 和 n₀，使得当 n ≥ n₀ 时，T(n) ≤ C·f(n)。大 O 记号描述的是 T(n) 的渐近上界。
计算规则：
- 加法规则：T(n) = T₁(n) + T₂(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
- 乘法规则：T(n) = T₁(n) × T₂(n) = O(f(n)) × O(g(n)) = O(f(n) × g(n))
- 只保留最高阶项，去掉系数
常见时间复杂度的大小关系：
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)| 复杂度 | 名称 | 典型算法 |
|---|---|---|
| O(1) | 常数阶 | 哈希查找、数组按下标访问 |
| O(log n) | 对数阶 | 折半查找、BST 查找（平均） |
| O(n) | 线性阶 | 顺序查找、遍历 |
| O(n log n) | 线性对数阶 | 快速排序、归并排序、堆排序 |
| O(n²) | 平方阶 | 冒泡排序、直接插入排序、简单选择排序 |
| O(2ⁿ) | 指数阶 | 穷举子集 |
分析方法
最好情况、最坏情况和平均情况：
| 情况 | 含义 | 考研中的用法 |
|---|---|---|
| 最好时间复杂度 | 输入最有利时的运行时间 | 参考价值有限 |
| 最坏时间复杂度 | 输入最不利时的运行时间 | 考试默认就是最坏情况 |
| 平均时间复杂度 | 所有可能输入的加权平均 | 需要时会明确说明 |
常见分析模式：
c
// 模式 1：单层循环 → O(n)
for (int i = 0; i < n; i++)
x++;
// 模式 2：双层嵌套循环 → O(n²)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
x++;
// 模式 3：对数循环 → O(log n)
int i = 1;
while (i <= n)
i = i * 2; // 执行次数 = ⌈log₂n⌉
// 模式 4：循环变量倍增 → O(√n)
for (int i = 0; i * i <= n; i++)
x++;
// 模式 5：嵌套但内层与外层相关 → O(n²)
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++) // 总次数 = 0+1+2+...+(n-1) = n(n-1)/2
x++;空间复杂度
空间复杂度 S(n) = O(g(n))，度量的是算法除输入数据外额外需要的辅助空间。
| 空间复杂度 | 含义 | 示例 |
|---|---|---|
| O(1) | 原地工作，只用常数个额外变量 | 冒泡排序、直接插入排序 |
| O(n) | 需要与输入规模同量级的辅助空间 | 归并排序的辅助数组 |
| O(log n) | 递归深度为 log n | 快速排序的递归栈（平均） |
| O(n) | 递归深度为 n | 快速排序的递归栈（最坏） |
注意：递归算法的空间复杂度 = 递归调用的深度（每层递归在栈上占用常数空间时）。
考研高频考点
- ⭐ 给定代码段，分析时间复杂度（选择题/应用题几乎每年必考）
- ⭐ 常见复杂度的大小排序（选择题）
- ⭐ 递归算法的时间/空间复杂度分析（难度较高，应用题偶考）
- ⭐ 算法的五个特性（选择题）
- 大 O 记号的数学定义
- 最好/最坏/平均时间复杂度的区别
- 空间复杂度的含义（不包含输入数据占用的空间）
易错：时间复杂度分析的是基本操作的执行次数，不是具体运行时间。O(n) 的算法不一定比 O(n²) 的算法快——大 O 描述的是增长趋势，只在 n 足够大时才有意义。
易错：算法的有穷性和程序的区别——程序可以无穷（如操作系统的主循环），但算法必须有穷。算法可以用自然语言、流程图、伪代码等描述，不一定要写成程序。
易错：分析空间复杂度时，形参也要考虑。函数的形参（如传入的数组指针）不算额外空间，但如果是传值调用（拷贝整个数组），则需要算入。