算法的五大特性#

易错：有穷性强调”会停下来”，确定性强调”没有歧义”，两者是不同的概念。408 选择题经常将这两个特性放在一起让考生辨析。

好算法的四个目标#

渐近记号#

• 大 O 记号是 408 考研中使用最频繁的记号。默认情况下，题目问”时间复杂度”通常指最坏时间复杂度，并用大 O 表示。
• 大 O 记号忽略低阶项和常数系数，只保留最高阶项。

计算规则：

1. 加法规则：T(n) = T₁(n) + T₂(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
2. 乘法规则：T(n) = T₁(n) × T₂(n) = O(f(n)) × O(g(n)) = O(f(n) × g(n))

常见时间复杂度排序#

1
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

典型分析模式#

1
// 模式 1：单层循环 → O(n)
2
for (int i = 0; i < n; i++)
3
    x++;
4

5
// 模式 2：双层嵌套循环 → O(n²)
6
for (int i = 0; i < n; i++)
7
    for (int j = 0; j < n; j++)
8
        x++;
9

10
// 模式 3：对数循环 → O(log n)
11
int i = 1;
12
while (i <= n)
13
    i = i * 2;   // 执行次数 = ⌈log₂n⌉
14

15
// 模式 4：循环变量倍增 → O(√n)
16
int i = 0;
17
while (i * i <= n)
18
    i++;
19

20
// 模式 5：嵌套但内层与外层相关 → O(n²)
21
for (int i = 0; i < n; i++)
22
    for (int j = 0; j < i; j++)   // 总次数 = 0+1+2+...+(n-1) = n(n-1)/2
23
        x++;

易错：判断循环复杂度时，不要只看有几层循环，还要看循环变量的变化方式。对数是 O(log n) 而不是 O(n)，倍增/减半（i*=2 / i/=2）是对数增长的典型特征。

最好、最坏与平均时间复杂度#

递归算法的时间复杂度#

递归算法的时间复杂度分析通常通过递推公式进行。常见形式：

• T(n) = T(n-1) + O(1) → O(n)（如递归遍历链表）
• T(n) = 2T(n/2) + O(n) → O(n log n)（如归并排序）
• T(n) = T(n/2) + O(1) → O(log n)（如折半查找的递归版）
• T(n) = 2T(n-1) + O(1) → O(2ⁿ)（如斐波那契数列的朴素递归）

主定理（Master Theorem）：对于形如 T(n) = aT(n/b) + f(n) 的递推式，主定理提供了快速求解渐近紧界的框架。408 考研中可以直接用递推展开法求解，主定理可作为补充。

常见空间复杂度#

注意：递归算法的空间复杂度 = 递归调用的深度（每层递归在栈上占用常数空间时）。

传值与传指针的空间开销#

• 传值（Pass by Value）：将实参的完整副本传递给函数。如果实参是大型结构体（如包含大量元素的数组），传值会造成 O(n) 的额外空间开销。
• 传指针/引用（Pass by Pointer/Reference）：只传递地址（4 或 8 字节），无论实参多大，空间开销始终为 O(1)。408 伪代码中的 & 符号（C++ 引用）即表示传引用。

易错：分析空间复杂度时，函数的形参也需要考虑。传入的数组指针本身（4 或 8 字节）不算额外空间，但如果函数通过传值方式接收整个数组，则需要将数组大小计入空间复杂度。