算法复杂度分析基础

概念

算法复杂度刻画的是"问题规模 $n$ 增长时，算法的开销以什么速度增长"，分两个维度：

• 时间复杂度（time complexity）：基本操作的执行次数随 $n$ 的增长趋势；
• 空间复杂度（space complexity）：除输入本身外，额外占用的存储空间随 $n$ 的增长趋势。

关键在"渐进"两个字：复杂度忽略常数因子和低阶项。$3n^2+5n+100$ 和 $n^2$ 被认为是同一档，因为当 $n$ 足够大时，$n^2$ 项压倒一切。

大 O 记号（big-O notation）的数学定义：

若存在正常数 $c$ 和 $n_0$，使得当 $n\ge n_0$ 时恒有 $0\le f(n)\le c\cdot g(n)$，则记 $f(n)=O(g(n))$。

换成白话：$g(n)$ 是 $f(n)$ 从某个规模之后都压得住的上界。

一句话理解：复杂度不是"跑得多久"，而是"数据量翻倍时，耗时涨几倍"。$O(n)$ 涨 2 倍，$O(n^2)$ 涨 4 倍，$O(\log n)$ 几乎不涨——这才是分档的意义。

原理

一、四个记号

记号	名称	定义（$\mathrm{\exists }c,n_0>0$，当 $n\ge n_0$）	直观
$O$	渐进上界	$0\le f(n)\le c\cdot g(n)$	$f$ 长得不快于 $g$
$\mathrm{\Omega }$	渐进下界	$0\le c\cdot g(n)\le f(n)$	$f$ 长得不慢于 $g$
$\mathrm{\Theta }$	紧确界	$c_{1}g(n)\le f(n)\le c_{2}g(n)$	$f$ 与 $g$ 同阶
$o$	严格小	对任意 $c>0$ 都有 $f(n)<c\cdot g(n)$	$f$ 比 $g$ 低阶，如 $2n=o(n^2)$

以 $f(n)=3n^2+2n+1$ 为例逐个验证：

① 证明 $f(n)=O(n^2)$：取 $c=6$、$n_0=1$，当 $n\ge 1$ 时

$$3n^2+2n+1\le 3n^2+3n^2+3n^2=9n^2(\text{取 }c=9\text{ 亦可})$$

代 $n=1$：左边 $=6$，右边 $c\cdot n^2=6$ ✅；$n=2$：左 $17$，右 $24$ ✅。故成立。

② 证明 $f(n)=\mathrm{\Omega }(n^2)$：取 $c=3$、$n_0=1$，则 $3n^2+2n+1\ge 3n^2$ ✅。

③ 由 ①② 得 $f(n)=\mathrm{\Theta }(n^2)$。

④ $f(n)$ 也是 $O(n^3)$、$O(2^n)$，却不是 $\mathrm{\Theta }(n^3)$。 这里有个关键区别：上界可以很松，$O$ 只是"不超过"。写 $f(n)=O(n^3)$ 没错，但不"紧"。408 里说"某算法的时间复杂度是 $O(\cdot )$"时，隐含要求写最紧的那个上界。

二、常见复杂度阶与大小关系

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

$n=1024$	$1$	${\log }_{2}n$	$n$	$n{\log }_{2}n$	$n^2$	$n^3$	$2^n$
取值	1	10	1024	10240	1 048 576	1.07×10⁹	大得无法写出

三条要紧的补充：

1. 对数的底数不影响阶：${\log }_{a}n={\displaystyle \frac{{\log }_{b}n}{{\log }_{b}a}}$，换底只差一个常数。所以写 $\log n$ 不必标底数。
2. ${\log }^{2}n$ 与 $n$ 之间仍是 ${\log }^{2}n<n$（$n$ 足够大时），但 ${\log }^{2}n$ 与 $\log n$ 不同阶。
3. $O(2^n)$、$O(n!)$ 属"指数级"，通常等价于"不可行"。$n=30$ 时 $2^{30}\approx {10}^9$ 已接近可接受上限。

三、两条运算规则

加法规则（顺序执行，取大）：若一段代码分两段，代价分别是 $O(f)$ 与 $O(g)$

$$O(f)+O(g)=O(max(f,g))$$

乘法规则（嵌套/循环相乘）：

$$O(f)\times O(g)=O(f\cdot g)$$

例：循环体内调用一次 $O(\log n)$ 的折半查找、循环 $n$ 次 → $O(n\log n)$。

四、最好 / 最坏 / 平均

情况	含义	典型例子
最好	最有利输入下的代价	直接插入排序正序输入 $O(n)$
最坏	最不利输入下的代价	快速排序逆序输入 $O(n^2)$
平均	按输入出现概率加权的期望代价	顺序查找等概率时 $(n+1)/2$

408 默认问的是最坏情况；只有题目明确说"平均"时才按等概率期望算。

五、空间复杂度

只算辅助空间，不算输入数据本身占的空间。

情形	空间复杂度	说明
只用了有限个变量	$O(1)$，称原地（in-place）	冒泡、插入、堆排序
开了一个与 $n$ 等长的数组	$O(n)$	归并排序的辅助数组
递归	至少 $O(\text{栈深度})$	必须把调用栈算进去

递归的空间一定要算栈深：递归求 $n!$ 的栈深是 $n$ → $O(n)$；快排期望栈深 $O(\log n)$、最坏 $O(n)$。这两条是选择题常客。

六、递归式的求解：三种方法

分治算法的时间通常写成递归式，例如 $T(n)=2T(n/2)+n$。求解有三条路：

1. 代入法（guess & verify）

猜出答案，再用数学归纳法验证。麻烦但通用。

2. 递归树（recursion tree）

把递归展开成一棵树，每层代价相加。

$$T(n)=2T(n/2)+n$$

                  n                ← 第 0 层：代价 n
              /       \
            n/2       n/2          ← 第 1 层：两个 n/2，代价 n
           /   \     /   \
         n/4  n/4  n/4  n/4        ← 第 2 层：四个 n/4，代价 n
          ...    ...    ...
         每层代价都是 n，共 log2 n + 1 层（到底部 n/2^k = 1）

$$T(n)=\underset{{\log }_{2}n+1\text{项}}{\underbrace{n+n+\cdots +n}}=n({\log }_{2}n+1)=\mathrm{\Theta }(n{\log }_{2}n)$$

3. 主定理（Master theorem）—— 首选

对形如

$$T(n)=aT(n/b)+f(n),a\ge 1,b>1$$

的递归式，记临界指数 $c={\log }_{b}a$，把 $f(n)$ 与 $n^c$ 比大小：

情形	条件	结论
① $f$ 更小	$f(n)=O(n^{c-\epsilon })$，$\epsilon >0$	$T(n)=\mathrm{\Theta }(n^c)$
② 同阶	$f(n)=\mathrm{\Theta }(n^c)$	$T(n)=\mathrm{\Theta }(n^c\log n)$
③ $f$ 更大	$f(n)=\mathrm{\Omega }(n^{c+\epsilon })$ 且满足正则条件	$T(n)=\mathrm{\Theta }(f(n))$

四个必背结果：

递归式	出处	主定理判据	结果
$T(n)=2T(n/2)+n$	归并排序、快排平均	$c={\log }_{2}2=1$，$f=\mathrm{\Theta }(n^1)$ → 情形②	$\mathrm{\Theta }(n\log n)$
$T(n)=2T(n/2)+1$	遍历二叉树全部结点	$c=1$，$f=1=O(n^{1-\epsilon })$ → 情形①	$\mathrm{\Theta }(n)$
$T(n)=T(n/2)+1$	折半查找	$c={\log }_{2}1=0$，$f=1=\mathrm{\Theta }(n^0)$ → 情形②	$\mathrm{\Theta }(\log n)$
$T(n)=T(n-1)+n$	快排最坏、冒泡	$b$ 不满足 $b>1$，主定理不适用	$\mathrm{\Theta }(n^2)$（展开求）

最后一条要特别记住：主定理只处理"规模缩小到 $1/b$"的情形，$T(n-1)$ 这种"每次只少一个元素"的必须手动展开。

示例

例 1：嵌套循环（完整列式）

for (i = 1; i <= n; i++)
    for (j = 1; j <= i; j++)
        s++;                       /* 基本操作 */

第一步，看内层：对固定的 $i$，内层执行 $i$ 次。

第二步，对 $i$ 求和：

$$\sum _{i=1}^{n}i=1+2+\cdots +n=\frac{n(n+1)}{2}$$

第三步，取最高阶：

$$T(n)=\frac{n^2+n}{2}=O(n^2)$$

结论：$O(n^2)$。注意不能因为"内层看起来不是每次都跑满 $n$ 次"就写 $O(n\log n)$——把求和算出来，这是最稳的做法。

例 2：对数阶循环（完整列式）

i = 1;
while (i <= n)
    i = i * 2;

第一步，列出 $i$ 的取值序列：

$$1,2,4,8,\dots ,2^k$$

第二步，确定循环次数：循环在 $2^k\le n<2^{k+1}$ 时进行，最后一次执行后 $i$ 变成 $2^{k+1}>n$ 退出。

$$k=\lfloor {\log }_{2}n\rfloor ,\text{执行次数}=k+1$$

第三步：$T(n)=\lfloor {\log }_{2}n\rfloor +1=O(\log n)$。

实测对照：$n=1\to 1$ 次，$n=8\to 4$ 次，$n=10\to 4$ 次，$n=1024\to 11$ 次——正好是 $\lfloor {\log }_{2}n\rfloor +1$。

同理：for (i = 1; i <= n; i *= 2) for (j = 1; j <= n; j++) 是 $O(n\log n)$（外层 $\log n$ 次 × 内层 $n$ 次）。

例 3：四个递归式的完整求解

① $T(n)=2T(n/2)+n$（归并排序）

递归树法：每层总代价都是 $n$，递归到 $n/2^k=1$ 即 $k={\log }_{2}n$，

$$T(n)=n\cdot ({\log }_{2}n+1)=\mathrm{\Theta }(n\log n)$$

主定理法：$a=2$、$b=2$、$c={\log }_{2}2=1$，$f(n)=n=\mathrm{\Theta }(n^1)$ → 情形② → $\mathrm{\Theta }(n\log n)$ ✅ 两法一致。

② $T(n)=2T(n/2)+1$（遍历二叉树）

递归树法：第 $k$ 层有 $2^k$ 个结点，每个代价 1，故第 $k$ 层代价 $2^k$；最底层 $k={\log }_{2}n$，

$$T(n)=\sum _{k=0}^{{\log }_{2}n}{2}^k=2^{{\log }_{2}n+1}-1=2n-1=\mathrm{\Theta }(n)$$

主定理法：$c=1$，$f(n)=1=O(n^{1-\epsilon })$ → 情形① → $\mathrm{\Theta }(n^1)=\mathrm{\Theta }(n)$ ✅

③ $T(n)=T(n/2)+1$（折半查找）

展开：$T(n)=1+1+\cdots$，直到 $n/2^k=1$，共 ${\log }_{2}n+1$ 项 → $\mathrm{\Theta }(\log n)$。

④ $T(n)=T(n-1)+n$（快排最坏、冒泡）

逐层展开：

$$T(n)=n+(n-1)+(n-2)+\cdots +1=\frac{n(n+1)}{2}=\mathrm{\Theta }(n^2)$$

结论汇总：$n$ 个元素递归，"每层代价 $n$、共 $\log n$ 层"是 $\mathrm{\Theta }(n\log n)$；"每层代价递减、共 $n$ 层"是 $\mathrm{\Theta }(n^2)$。看清是"层数 × 每层代价"还是"等差求和"，就能一眼判断。

例 4：空间复杂度分析

/* 版本 A：非递归，只用了 3 个变量 —— 空间 O(1) */
int sumA(int n) {
    int s = 0;
    for (int i = 1; i <= n; i++) s += i;
    return s;
}

/* 版本 B：递归，栈深 n —— 空间 O(n) */
int sumB(int n) {
    return n <= 1 ? n : n + sumB(n - 1);
}

两个版本时间复杂度都是 $O(n)$（各做 $n$ 次加法），但空间复杂度一个是 $O(1)$、一个是 $O(n)$。选择/填空题最爱这样成对比较。

例 5：实测操作次数验证复杂度

#include <stdio.h>

/* 统计三种循环结构实际执行了多少次，用数据验证阶的结论 */
int main(void) {
    int ns[] = {8, 64, 512, 4096};
    printf("%8s %12s %12s %12s %10s\n", "n", "O(n)", "O(n^2)", "O(n log2 n)", "O(log2 n)");
    for (int t = 0; t < 4; t++) {
        int n = ns[t];
        long c1 = 0, c2 = 0, c3 = 0; int c4 = 0;

        for (int i = 0; i < n; i++) c1++;                        /* O(n) */
        for (int i = 0; i < n; i++)                              /* O(n^2) */
            for (int j = 0; j < n; j++) c2++;
        for (int i = 1; i <= n; i *= 2)                          /* O(n log n) */
            for (int j = 0; j < n; j++) c3++;
        for (int i = 1; i <= n; i *= 2) c4++;                    /* O(log n) */

        printf("%8d %12ld %12ld %12ld %10d\n", n, c1, c2, c3, c4);
    }
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

按输出反推阶（$n$ 从 8 涨到 4096，即规模涨 512 倍）：

列	8 时的次数	4096 时的次数	涨幅	对应阶
$O(n)$	8	4096	512 倍	线性
$O(n^2)$	64	16 777 216	262 144 倍 = ${512}^2$	平方
$O(n\log n)$	32	53 248	1664 倍 ≈ $512\times 3.25$	$n\log n$
$O(\log n)$	4	13	3.25 倍	对数

看涨幅就能定阶：规模涨 512 倍 → 线性阶涨 512 倍、平方阶涨 ${512}^2$、"$n\log n$"阶涨 $512$ 再乘上 $\log$ 部分的增长（这里是 $13/4=3.25$）、对数阶几乎不涨。比死记公式可靠得多。

Python 对照

from math import log2, floor

def count_n(n):        return n                              # 单层循环
def count_n2(n):       return n * n                          # 双层循环
def count_nlogn(n):
    c, i = 0, 1
    while i <= n:                                            # 外层 log n 次
        c += n; i *= 2                                       # 内层 n 次
    return c
def count_logn(n):
    c, i = 0, 1
    while i <= n:
        c += 1; i *= 2
    return c

print(f"{'n':>8}{'n':>10}{'n^2':>14}{'nlogn':>12}{'logn':>8}")
for n in (8, 64, 512, 4096):
    print(f"{n:>8}{count_n(n):>10}{count_n2(n):>14}{count_nlogn(n):>12}{count_logn(n):>8}")

# 用"翻倍比"看阶：n 翻倍时各类开销涨几倍
print("\n规模翻倍时的涨幅（比值 → 阶）:")
for f, name in [(count_n, "O(n)"), (count_n2, "O(n^2)"), (count_nlogn, "O(n log n)"), (count_logn, "O(log n)")]:
    r = f(4096) / f(2048)
    print(f"  {name:>10}: {r:.2f} 倍")

# 递归式验证：T(n)=2T(n/2)+n 的实际基本操作次数
def merge_cost(n):
    if n <= 1: return 0
    return 2 * merge_cost(n // 2) + n
print("\nT(n)=2T(n/2)+n 实测:", {n: merge_cost(n) for n in (4, 8, 16, 64)})
print("对照 n*log2(n)  :", {n: n * log2(n) for n in (4, 8, 16, 64)})

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

考点

考点

1. 全书复杂度速查表（408 综合题的公共素材）

结构 / 算法	平均	最坏	空间	备注
顺序表按下标访问	$O(1)$	$O(1)$	—	随机存取
顺序表插入/删除	$O(n)$	$O(n)$	$O(1)$	搬元素
单链表按下标访问	$O(n)$	$O(n)$	—	顺序存取
单链表插入/删除（已知位置）	$O(1)$	$O(1)$	$O(1)$	改指针
栈 / 队列操作	$O(1)$	$O(1)$	—	——
二叉树遍历	$O(n)$	$O(n)$	$O(n)$ 栈	每结点一次
二叉排序树查找	$O(\log n)$	$O(n)$	—	退化成单枝时最坏
AVL 查找 / 插入	$O(\log n)$	$O(\log n)$	—	始终平衡
堆：插入 / 删除堆顶	$O(\log n)$	$O(\log n)$	$O(1)$	取最值 $O(1)$
建堆	$O(n)$	$O(n)$	$O(1)$	自底向上
图的 DFS / BFS（邻接表）	$O(n+e)$	$O(n+e)$	$O(n)$	邻接矩阵是 $O(n^2)$
Prim（邻接矩阵）	$O(n^2)$	$O(n^2)$	$O(n)$	稠密图
Kruskal	$O(e\log e)$	$O(e\log e)$	$O(e)$	稀疏图
Dijkstra（邻接矩阵）	$O(n^2)$	$O(n^2)$	$O(n)$	不能有负权
Floyd	$O(n^3)$	$O(n^3)$	$O(n^2)$	全源最短路
拓扑排序	$O(n+e)$	$O(n+e)$	$O(n)$	——
顺序查找	$O(n)$	$O(n)$	$O(1)$	——
折半查找	$O(\log n)$	$O(\log n)$	$O(1)$	需有序 + 顺序存储
散列表查找	$O(1)$	$O(n)$	$O(n)$	与装填因子 $\alpha$ 有关
八大排序	见 归并排序与基数排序 的总结表

2. 阶排序（必背）

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

3. 主定理判据（三步走）

1. 写出 $a$、$b$、$f(n)$，算出 $c={\log }_{b}a$；
2. 把 $f(n)$ 与 $n^c$ 比大小（更小 / 同阶 / 更大）；
3. 对应取 $n^c$、$n^c\log n$、或 $f(n)$。

前提检查：$a\ge 1$、$b>1$。像 $T(n)=T(n-1)+n$ 这种直接展开。

4. 易错点

• $O$ 是上界，$O(n^2)$ 的算法同时也是 $O(n^3)$。题目问"时间复杂度是多少"，答最紧的上界。
• 对数底数可省略，${\log }_{2}n$、${\log }_{10}n$、$\ln n$ 同阶；但 ${\log }^{2}n$ 与 $\log n$ 是不同阶，${\log }^{2}n$ 比 $\log n$ 大。
• 空间复杂度不含输入数据。排序算法的"$O(1)$ 空间"指辅助空间，不是说输入不占内存。
• 递归必须把栈算进空间：$O(\log n)$ 或 $O(n)$ 都可能，取决于递归深度。归并排序写 $O(n)$ 而不是 $O(\log n)$。
• "平均复杂度"要用概率加权，不是把最好和最坏取算术平均。快排平均是 $O(n\log n)$，不是 $(O(n\log n)+O(n^2))/2$。
• 循环里的"乘法"要看清是乘自己还是乘常数：i *= 2 是 $\log n$；i += 2 是 $n/2$（仍为 $O(n)$）；i++ 是 $n$。
• 两层循环不一定 $O(n^2)$：内层边界依赖外层（如例 1）要老老实实求和；内层是 $\log$ 规模就变成 $O(n\log n)$。
• 复杂度与机器无关，但与"基本操作的选取"有关。同一算法按"比较次数"算和按"移动次数"算可能给出不同阶（如简单选择排序：比较 $O(n^2)$，移动 $O(n)$）。题目说什么就是什么。
• 阶不等于实际快慢：$n$ 很小时，$O(n^2)$ 的实现可能因为常数小反而比 $O(n\log n)$ 快。复杂度只描述增长趋势。

5. 408 常见问法

• "以下代码段的时间复杂度是"→ 直接算循环次数；
• "下列排序算法中，时间复杂度为 $O(n\log n)$ 且稳定的是"→ 归并（详见 43 篇总结表）；
• "递归算法的空间复杂度主要取决于"→ 递归深度；
• 综合题里给出递推式让求渐进阶 → 优先用主定理，套不上就展开。

小结

• 复杂度是渐进度量：忽略常数与低阶项，只看增长趋势。
• 四个记号里 $O$ 是上界、$\mathrm{\Omega }$ 是下界、$\mathrm{\Theta }$ 是同阶；$O$ 不唯一，答题写最紧的那个。
• 两条规则：顺序取大（加法）、嵌套相乘（乘法）；$\log n$ 的底数一律可省。
• 递归式首选主定理：算 $c={\log }_{b}a$，比较 $f(n)$ 与 $n^c$；$b=1$ 的情形（$T(n-1)$）必须手动展开。
• 空间只算辅助空间，递归必算栈深。
• 数据结构部分到此收口。回顾这条线的脉络：线性结构 → 树形结构 → 图 → 查找 → 排序 → 复杂度，每一步都在回答"用什么方式组织数据，才能让某类操作更快"。而"更快"的极限，最终由计算机底层的存储层次与电路速度决定——这正是下一门课的主题。

下一篇：计算机系统概述（进入 L2 机器层 · 计算机组成原理）