算法复杂度分析（大 O 表示法）

为什么关注复杂度

复杂度回答一个问题：当输入规模 n 增大时，程序会慢多少、占多少内存？

• 两台机器、编译器优化、CPU 频率只影响常数倍；算法复杂度的差异是数量级差异。
• 例如 n = 10⁶ 时：O(n) 约 10⁶ 次操作，O(n²) 约 10¹² 次操作，差距不是调参能弥补的。
• 面试里「这段代码的时间复杂度是多少」考的正是：不跑代码，能否一眼读出增长量级。

大 O 表示法

大 O 给出复杂度的上界，表示「最坏情况下，随 n 增长，工作量最多按某个量级增长」。

记 f(n) = O(g(n))，含义：存在常数 c 与 n₀，当 n ≥ n₀ 时有 f(n) ≤ c · g(n)。

核心约定：只保留增长最快的主导项，去掉常数系数与低阶项。

3n² + 5n + 100  →  O(n²)     // n² 主导，5n 与常数 100 是低阶项
2n log n + n    →  O(n log n) // n log n 主导

为什么可以忽略常数？因为 n 足够大时，3n² 和 n² 差的是固定 3 倍，但 n² 和 n 差的是 n 倍——后者才是致命的。大 O 只关心「量级」。

如何判断时间复杂度

拿到一段代码，按下面几条规则从上往下算。

规则一：顺序执行相加，嵌套相乘

// O(n) + O(n) = O(n)
for (int i = 0; i < n; i++) a[i]++;      // 第一段 O(n)
for (int i = 0; i < n; i++) b[i]--;      // 第二段 O(n)
// 顺序执行：O(n) + O(n) = O(2n) = O(n)

// O(n) * O(n) = O(n²)  ← 双重循环的由来
for (int i = 0; i < n; i++) {            // 外层跑 n 次
    for (int j = 0; j < n; j++) {        // 内层每次跑 n 次
        c[i][j] = a[i] + b[j];           // 总共 n × n 次
    }
}

要点：数循环层数，看每层各跑多少次，乘起来就是工作量。

规则二：循环变量每次减半/翻倍 → O(log n)

// 每次 i 翻倍：1, 2, 4, 8, ..., 2^k ≥ n → k = log₂n 次
for (int i = 1; i < n; i *= 2) {
    // O(log n)
}

// 每次区间减半：n, n/2, n/4, ..., 1 → log₂n 次
while (n > 1) {
    n /= 2;      // 二分查找的内核
}

只要循环变量按固定比例缩小/放大（÷2、×3 都算），复杂度就是 O(log n)。对数底数在大 O 里被忽略：log₂n、log₁₀n 只差常数倍。

规则三：递归——画递归树或写递推式

递归复杂度的推导分两步：写递推式 → 套主定理或展开递归树。

以归并排序为例，T(n) = 2T(n/2) + O(n)：每一层把问题拆成两半（2T(n/2)），再把有序两半合并（O(n)）。递归树共 log n 层，每层总工作量都是 O(n)，所以 O(n) × log n = O(n log n)。

规则四：分治快排/归并 → O(n log n) 的推导思路

• 归并排序：稳定 O(n log n)。递推式 T(n) = 2T(n/2) + O(n)，每层 O(n)、共 log n 层。
• 快速排序：平均 O(n log n)，最坏 O(n²)。平均每次 partition 约把数组分成两半，同样满足 2T(n/2) + O(n)；但若每次 pivot 都取到极值（如已有序数组取头元素），退化成 T(n) = T(n-1) + O(n)，即 O(n²)。

这就是「分治每次均分 → n log n，每次只切掉一个 → n²」的本质区别。

常见复杂度对照表

记忆锚点：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)，从「随便跑」到「n 稍大就跑不动」。

主定理速查

对形如 T(n) = a · T(n/b) + f(n) 的递推式（拆成 a 个子问题、每个规模 n/b、合并代价 f(n)），记 c = log_b a：

1. 若 f(n) = O(n^(c-ε))（合并代价比拆分子问题更轻）→ T(n) = Θ(n^c)
2. 若 f(n) = Θ(n^c)（合并代价与子问题同阶）→ T(n) = Θ(n^c · log n)
3. 若 f(n) = Ω(n^(c+ε)) 且满足正则条件（合并代价占主导）→ T(n) = Θ(f(n))

三个高频实例：

二分查找  T(n) = T(n/2) + O(1)   → a=1,b=2,c=0, f(n)=Θ(n⁰) → 情况2 → O(log n)
归并排序  T(n) = 2T(n/2) + O(n)   → a=2,b=2,c=1, f(n)=Θ(n¹) → 情况2 → O(n log n)
快速排序(平均) 同上 → O(n log n)；最坏 T(n)=T(n-1)+O(n) → O(n²)

空间复杂度

空间复杂度衡量额外占用的内存（不含输入本身），同样用大 O 表示。

判断三处：

1. 辅助数组：归并排序合并时开辟 O(n) 临时数组；原地算法（冒泡、插入、快排原地分区）只占 O(1) 或 O(log n)。
2. 递归调用栈：递归深度就是栈占用。二分查找递归深度 log n → O(log n)；快排最坏递归深度 n → O(n)。
3. 原地 vs 非原地：是否复用输入数组空间。

// 空间 O(n)：额外开了一个等长数组
vector<int> tmp(n);
for (int i = 0; i < n; i++) tmp[i] = a[i] * 2;

// 空间 O(log n)：递归深度 log n 的栈
void dfs(int l, int r) {          // 每次区间减半
    if (l >= r) return;
    int mid = (l + r) / 2;
    dfs(l, mid);
    dfs(mid + 1, r);
}

记忆口诀：时间复杂度看「循环和递归的层数」，空间复杂度看「递归栈深度 + 是否新开数组」。

实战：推一遍排序算法的复杂度

推导示范——归并排序：

void mergeSort(vector<int>& a, int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(a, l, mid);      // T(n/2)
    mergeSort(a, mid + 1, r);  // T(n/2)
    merge(a, l, mid, r);       // O(n) 合并 + O(n) 临时数组
}

• 时间：T(n) = 2T(n/2) + O(n)，主定理情况 2 → O(n log n)。
• 空间：每次合并需要 O(n) 临时数组（递归栈 O(log n) 被 O(n) 主导）→ O(n)。

推导示范——冒泡排序（双重循环，无减半，无分治）：

for (int i = 0; i < n - 1; i++)          // 外层 n 次
    for (int j = 0; j < n - 1 - i; j++)  // 内层平均 n/2 次
        if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);

• 嵌套相乘：约 n × n/2 次 → O(n²)；无递归、无辅助数组 → 空间 O(1)。

更多排序细节与代码实现见 排序算法。