欢迎阅读本篇绪论，开启美妙（bushi）的数据结构与算法分析之旅，本篇文章将详细介绍数据结构与算法的时间复杂度或者空间复杂度的前置知识，以便后续深入学习

---

先从时间复杂度入手，接下来三个部分，分别是计算时间复杂度常用的数学符号，产生时间复杂度的行为，与求解时间复杂度的常见方法（甚至罕见，Ph1z倾情呈现），第四部分则是空间复杂度，希望读者看完这些能有较大收获喵（下文中打*的部分可以略看，了解即可，以及提供的实战例子会在未来出现，仅帮助初学但没有实例的人找到能计算的实例，以及参考我/ai的过程）

---

第一部分：渐进记号基础

为什么我们需要渐进记号捏？ 因为精确计数太麻烦，$3n^2+7n+42$ 和 $n^2$ 在 $n\to \mathrm{\infty }$ 时"长得一样快"，我们只想抓住增长趋势这个本质，忽略常数因子和低阶项的细节。渐进记号就是做这件事的数学工具，用来描述复杂度的阶。

1.1 渐进记号的数学定义

1.1.1 Θ 记号（渐进紧界）

读作 大Theta

定义： 对于给定函数 $g(n)$，定义集合：

$$\mathrm{\Theta }(g(n))=\{f(n)\mid \mathrm{\exists }{c}_1,c_2,n_0>0,\mathrm{\forall }n\ge n_0:0\le c_{1}g(n)\le f(n)\le c_{2}g(n)\}$$

Ph1zの理解： $f(n)=\mathrm{\Theta }(g(n))$ 意味着 $f(n)$ 和 $g(n)$ 的增长速度"相同"，存在常数因子范围内的上下界。

严格证明示例： 证明 $\frac{1}{2}{n}^2-3n=\mathrm{\Theta }(n^2)$

• 需要找到 $c_1,c_2,n_0$ 使得对所有 $n\ge n_0$：$c_1{n}^2\le \frac{1}{2}{n}^2-3n\le c_2{n}^2$
• 右边：$\frac{1}{2}{n}^2-3n\le \frac{1}{2}{n}^2$，取 $c_2=\frac{1}{2}$
• 左边：当 $n\ge 7$ 时，$\frac{1}{2}{n}^2-3n\ge \frac{1}{14}{n}^2$，取 $c_1=\frac{1}{14},n_0=7$
• 因此 $\frac{1}{2}{n}^2-3n=\mathrm{\Theta }(n^2)$ ✓

1.1.2 O 记号（渐进上界）

读作 大O

定义：

$$O(g(n))=\{f(n)\mid \mathrm{\exists }c,n_0>0,\mathrm{\forall }n\ge n_0:0\le f(n)\le c\cdot g(n)\}$$

Ph1zの理解： $f(n)=O(g(n))$ 意味着 $f(n)$ 的增长速度不超过 $g(n)$（至多同阶）。

注意事项：

• $O$ 记号给出的是上界，但不一定是紧界
• 例如 $n=O(n^2)$ 成立，但 $n\ne \mathrm{\Theta }(n^2)$——就像说"我跑步速度 $=O$(光速)"，对的，但毫无信息量
• 在算法分析中，当我们说"时间复杂度为 $O(n\log n)$"时，一般认为这是一个紧界

1.1.3 Ω 记号（渐进下界）

读作 大Omega

定义：

$$\mathrm{\Omega }(g(n))=\{f(n)\mid \mathrm{\exists }c,n_0>0,\mathrm{\forall }n\ge n_0:0\le c\cdot g(n)\le f(n)\}$$

Ph1zの理解： $f(n)=\mathrm{\Omega }(g(n))$ 意味着 $f(n)$ 的增长速度不低于 $g(n)$（至少同阶）。

1.1.4 o 记号（非紧上界）*

读作 小O

定义：

$$o(g(n))=\{f(n)\mid \mathrm{\forall }c>0,\mathrm{\exists }{n}_0>0,\mathrm{\forall }n\ge n_0:0\le f(n)<c\cdot g(n)\}$$

等价定义： $f(n)=o(g(n))$ 当且仅当 $\underset{n\to \mathrm{\infty }}{lim}\frac{f(n)}{g(n)}=0$

示例： $n=o(n\log n)$，$n^2=o(n^3)$，但 $2n\ne o(n)$（$2n$ 和 $n$ 同量级，不会被甩开）

1.1.5 ω 记号（非紧下界）*

读作 小Omega

定义：

$$\omega (g(n))=\{f(n)\mid \mathrm{\forall }c>0,\mathrm{\exists }{n}_0>0,\mathrm{\forall }n\ge n_0:0\le c\cdot g(n)<f(n)\}$$

等价定义： $f(n)=\omega (g(n))$ 当且仅当 $\underset{n\to \mathrm{\infty }}{lim}\frac{f(n)}{g(n)}=\mathrm{\infty }$

1.2 渐进记号的性质*

1.2.1 传递性*

性质	关系	通俗解释
传递性	$f=O(g)\wedge g=O(h)\Rightarrow f=O(h)$	$f$ 不超 $g$，$g$ 不超 $h$ → $f$ 不超 $h$
传递性	$f=\mathrm{\Omega }(g)\wedge g=\mathrm{\Omega }(h)\Rightarrow f=\mathrm{\Omega }(h)$	$f$ 不低于 $g$，$g$ 不低于 $h$ → $f$ 不低于 $h$
传递性	$f=\mathrm{\Theta }(g)\wedge g=\mathrm{\Theta }(h)\Rightarrow f=\mathrm{\Theta }(h)$	同量级具有传递性
传递性	$f=o(g)\wedge g=o(h)\Rightarrow f=o(h)$	被甩开也传递
传递性	$f=\omega (g)\wedge g=\omega (h)\Rightarrow f=\omega (h)$	超越也传递

1.2.2 自反性*

• $f=\mathrm{\Theta }(f)$，$f=O(f)$，$f=\mathrm{\Omega }(f)$
• $f\ne o(f)$，$f\ne \omega (f)$

1.2.3 对称性与转置对称性*

• 对称性： $f=\mathrm{\Theta }(g)⟺g=\mathrm{\Theta }(f)$
• 转置对称性： $f=O(g)⟺g=\mathrm{\Omega }(f)$
• 转置对称性： $f=o(g)⟺g=\omega (f)$

1.2.4 常见函数的渐进比较（可自行证明）

对于任意小 $ \epsilon > 0$：

$$\begin{gathered} 1\prec \log \log n\prec \log n\prec (\log n{)}^2\prec n^{ϵ}\prec n\prec n\log n \\ \prec n^{1+ϵ}\prec 2^n\prec n!\prec n^n \end{gathered}$$

其中 $f\prec g$ 表示 $f=o(g)$。

用具体数字感受差距（$n=100$）：

函数	$n=100$ 时的值	量级感
$\log n$	$\approx 7$	一只手数得过来
$n$	$100$	教室里的人数
$n\log n$	$\approx 700$	一栋楼的人数
$n^2$	$\mathrm{10,000}$	一个小体育场
$2^n$	$\approx {10}^{30}$	无敌大
$n!$	$\approx {10}^{158}$	略（
$n^n$	${10}^{200}$	略（

1.2.5 三类情况下的渐进记号*

定理（CLRS 定理 3.1）： 对任意两个函数 $f(n)$ 和 $g(n)$，$f(n)=\mathrm{\Theta }(g(n))$ 当且仅当 $f(n)=O(g(n))$ 且 $f(n)=\mathrm{\Omega }(g(n))$。

Ph1zの理解： 上下界都卡住了，就是紧界。就像证明一个人的身高在 170~175cm 之间，既 $O(175\text{cm})$ 又 $\mathrm{\Omega }(170\text{cm})$，所以 $\mathrm{\Theta }$ 就是"大约 170 多 cm"。

1.3 常用函数的渐进公式

1.3.1 多项式

$$\sum _{k=0}^d{a}_k{n}^k=\mathrm{\Theta }(n^d)$$

其中 $a_d>0$，即多项式的渐进增长率由其最高次项决定。

1.3.2 对数

公式	说明	直觉
${\log }_{b}n=\mathrm{\Theta }(\log n)$	对数底数无关紧要（常数因子差异）	换底只差一个常数：${\log }_{b}n=\frac{\log n}{\log b}$
$\log (n!)=\mathrm{\Theta }(n\log n)$	Stirling 近似的推论	$\log (1\times 2\times \cdots \times n)\approx n\log n$，大部分项接近 $n$
$a^{{\log }_{b}n}=n^{{\log }_{b}a}$	对数换底的重要恒等式	主定理的核心！ $n^{{\log }_{b}a}$ 就是分治的"临界点"

1.3.3 Stirling 近似

$$n!=\sqrt{2\pi n}{\left(\frac{n}{e}\right)}^n(1+\mathrm{\Theta }\left(\frac{1}{n}\right))$$

部分推论（读者可以自行推导）：

• $\log (n!)=n\log n-n+O(\log n)$
• $n!=o(n^n)$
• $n!=\omega (2^n)$
• $\log (n!)=\mathrm{\Theta }(n\log n)$

---

第二部分：产生时间复杂度的行为

一、哪些行为会产生时间复杂度

时间复杂度衡量的是算法执行时间随输入规模增长的变化趋势。任何一条指令的执行都需要时间，但在分析中，我们关注的是与输入规模 n 相关的操作。

以下行为会产生时间复杂度（按重要程度排列）：

1. 基本操作

最核心的计数单位，通常选算法中最频繁执行的关键操作：

• 比较操作：if (a > b)
• 算术运算：a + b、a * b
• 赋值操作：a = b
• 数组索引访问：arr[i]
• 指针/引用操作

关键： 单个基本操作是 $O(1)$。复杂度来自基本操作被重复执行了多少次。

2. 循环结构——复杂度的最大来源

循环使基本操作重复执行，是时间复杂度的主要来源：

for (int i = 0; i < n; i++)   // 循环n次
    sum += arr[i];            // 基本操作执行n次 → O(n)

循环总复杂度的计算方法： 循环体执行次数 × 循环体内部复杂度 = 该循环的总复杂度

常见循环模式速查：

代码模式	执行次数	时间复杂度	直觉
for(i=0; i<n; i++)	$n$	$O(n)$	遍历一遍
for(i=1; i<n; i*=2)	$\log n$	$O(\log n)$	每次翻倍，很快到头
for(i=n; i>0; i/=2)	$\log n$	$O(\log n)$	每次减半，很快到头
嵌套两层 for(i=0; i<n; i++) for(j=0; j<n; j++)	$n\times n$	$O(n^2)$	遍历所有对
嵌套 for(i=0; i<n; i++) for(j=0; j<i; j++)	$\sum _{i=0}^{n-1}i=\frac{n(n-1)}{2}$	$O(n^2)$	三角形区域
for(i=1; i<n; i*=2) for(j=0; j<i; j++)	$\sum _{k=0}^{\log n}{2}^k=2n-1$	$O(n)$	几何级数！

3. 递归调用

每次递归调用都会产生函数调用开销，且递归深度和每层的工作量决定复杂度：

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // 递归n次 → O(n)
}

递归的思维方式： 把递归想象成一棵树——每个节点是一次调用，子节点是该次调用产生的更小调用。总工作量 = 所有节点的代价之和。

4. 函数调用

• 普通函数调用本身是 $O(1)$，但函数内部可能有循环
• 库函数有自己的复杂度，不能当作免费：

常见操作	复杂度	注意
sort()	$O(n\log n)$	C++ std::sort（introsort）
Arrays.sort() 基本类型	$O(n^2)$	Java Dual-Pivot Quicksort，最坏退化
Arrays.sort() 对象	$O(n\log n)$	TimSort，保证最坏 $O(n\log n)$
HashMap.get()	平均 $O(1)$，最坏 $O(n)$	哈希冲突时退化
Collections.sort()	$O(n\log n)$	基于归并排序（TimSort）
String.contains()	$O(n)$	线性扫描

5. 内存分配/释放*

• 栈上分配：$O(1)$
• 堆上分配（malloc/new）：通常视为 $O(1)$，但实际涉及系统调用，粗略分析时常看作常数时间

6. I/O 操作*

• 读写文件、网络传输、打印输出等，通常比内存操作慢几个数量级
• 在纯算法分析中常简化为 $O(1)$ 或单独考虑

关键原则：时间复杂度分析的核心是找出执行次数与输入规模 $n$ 成正比的操作，忽略常数因子和低阶项。

---

二、实战：从代码到复杂度

由内向外，逐层累乘循环次数

例 1：单层循环

for (int i = 0; i < n; i++) {
    printf("%d", arr[i]);  // O(1) 的基本操作
}
// 总：n × O(1) = O(n)

例 2：嵌套循环——独立变量

for (int i = 0; i < n; i++) {        // 外层 n 次
    for (int j = 0; j < m; j++) {    // 内层 m 次
        sum += arr[i][j];            // O(1)
    }
}
// 总：n × m × O(1) = O(nm)

例 3：嵌套循环——依赖变量

for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {    // j 跑到 i，不是 n！
        sum += arr[i][j];
    }
}
// 总：Σ(i=0..n-1) i = n(n-1)/2 = O(n²)

常见错误： 看到两层循环就写 $O(n^2)$。如果内层循环次数不是 $n$ 而是依赖外层变量，必须求和！

例 4：对数循环

int i = 1;
while (i < n) {
    i = i * 2;    // 每次翻倍
    // ... O(1) 操作
}
// i 的变化：1, 2, 4, 8, ..., n → 循环 log₂n 次
// 总：O(log n)

例 5：混合模式

for (int i = 1; i <= n; i *= 2) {       // log n 次
    for (int j = 0; j < i; j++) {       // i 次（随 i 变化！）
        sum++;
    }
}
// 总：Σ(k=0..log n) 2^k = 2n - 1 = O(n)
// 虽然有"两层循环"，但不是 O(n log n)！

常见错误： 不能机械地"循环层数 → 复杂度"，必须分析实际执行次数。

例 6：调用了库函数

for (int i = 0; i < n; i++) {
    sort(arr, arr + n);   // 每次 sort 是 O(n log n)！
}
// 总：n × O(n log n) = O(n² log n)

---

三、复杂度分析常见陷阱

陷阱	错误分析	正确分析
内层循环依赖外层	直接 $n\times n=O(n^2)$	要对内层求和：$\sum _{i}f(i)$
对数循环看成线性	while(i<n) i*=2 当成 $O(n)$	每次翻倍 → $O(\log n)$
忽略库函数代价	sort() 当 $O(1)$	sort() 是 $O(n\log n)$
多个分支取最好的	只看最短分支	应取最坏分支（上界）
最好=平均=最坏	对所有算法混为一谈	快排最坏 $O(n^2)$，平均 $O(n\log n)$

---

第三部分：标准递推式与主定理

3.1 递归树方法

方法 把递推式画成一棵树，根节点是当前层的工作量 $f(n)$，子节点是更小问题的递推调用。然后逐层求和。

3.1.1 方法步骤

1. 将递推式展开为树形结构（根 = 当前层，子节点 = 递归调用）
2. 计算每层的总代价（节点数 × 每个节点的代价）
3. 确定树的深度（递归到叶子需要几层）
4. 将所有层的代价求和 + 叶子节点的代价
5. 用代换法验证结果（递归树给出猜测，代换法严格证明）

3.1.2 详细示例：$T(n)=3T(n/4)+\mathrm{\Theta }(n^2)$

递归树展开（建议在纸上画出来）：

             cn²     ← 第0层：1个节点，代价 cn²
        /     |     \
    cn²/16 cn²/16 cn²/16  ← 第1层：3个节点，总代价 (3/16)cn²
      /|\    /|\    /|\
      ...    ...    ...         ← 第2层：9个节点，总代价 (3/16)²cn²

• 第 0 层（根）：代价 $c{n}^2$
• 第 1 层：3 个子节点，每个代价 $c(n/4{)}^2$，总代价 $3c(n/4{)}^2=(3/16)c{n}^2$
• 第 2 层：9 个子节点，每个代价 $c(n/16{)}^2$，总代价 $9c(n/16{)}^2=(9/256)c{n}^2=(3/16{)}^{2}c{n}^2$
• 第 $i$ 层：$3^i$ 个子节点，每个代价 $c(n/4^i{)}^2$，总代价 $(3/16{)}^{i}c{n}^2$
• 树的深度：${\log }_{4}n$
• 叶子层：$3^{{\log }_{4}n}=n^{{\log }_{4}3}$ 个叶子，每个代价 $\mathrm{\Theta }(1)$

总代价：

$$T(n)=\sum _{i=0}^{{\log }_{4}n-1}{\left(\frac{3}{16}\right)}^{i}c{n}^2+\mathrm{\Theta }\left(n^{{\log }_{4}3}\right)$$

几何级数 $\sum _{i=0}^{\mathrm{\infty }}(3/16{)}^i=\frac{16}{13}$ 收敛，因此：

$$T(n)=\mathrm{\Theta }(n^2)$$

与主定理情况 3（$a=3,b=4,n^{{\log }_{4}3}\approx n^{0.793}$，$f(n)=n^2=\mathrm{\Omega }(n^{0.793+ϵ})$）一致。

3.2 主定理（Master Theorem）（配合3.6食用更佳）

3.2.1 定理陈述

设 $T(n)$ 的递推式为：

$$T(n)=aT(n/b)+f(n)$$

参数含义：

• $a$：每次分出几个子问题（分支数）
• $n/b$：每个子问题的规模（缩小比例）
• $f(n)$：合并/划分这一层的工作量
• $n^{{\log }_{b}a}$：临界函数——所有叶子节点总工作量（如果叶子占主导）

其中 $a\ge 1$ 和 $b>1$ 是常数，$f(n)$ 是渐近正函数。定义临界值 $n^{{\log }_{b}a}$，则：

情况 1： 若对某个常数 $ϵ>0$，$f(n)=O(n^{{\log }_{b}a-ϵ})$，则：

$$T(n)=\mathrm{\Theta }(n^{{\log }_{b}a})$$

Ph1zの理解： 合并工作量 $f(n)$ 太小，叶子节点（递归到底的总工作量）占主导。就像搬运工搬砖——搬一块砖的时间可以忽略，主要时间花在"有很多小任务"本身。

情况 2： 若 $f(n)=\mathrm{\Theta }(n^{{\log }_{b}a})$，则：

$$T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}\log n)$$

Ph1zの理解： 合并工作量和叶子工作量刚好平衡，每层贡献差不多，乘以树高 $\log n$。归并排序就是这种情况——每层合并 $O(n)$，共 $\log n$ 层。

情况 3： 若对某个常数 $ϵ>0$，$f(n)=\mathrm{\Omega }(n^{{\log }_{b}a+ϵ})$，且对某个常数 $c<1$ 和所有足够大的 $n$，$af(n/b)\le cf(n)$（正则条件），则：

$$T(n)=\mathrm{\Theta }(f(n))$$

Ph1zの理解： 合并工作量 $f(n)$ 太大，根节点那一层就占了绝大部分。子问题的工作量加起来还不如合并开销。就像"准备工作比干活本身还耗时"。

3.2.2 主定理应用详例

使用步骤：

1. 从递推式中读出 $a$（子问题数）、$b$（缩小比例）、$f(n)$（合并代价）
2. 计算临界值 $n^{{\log }_{b}a}$
3. 比较 $f(n)$ 和 $n^{{\log }_{b}a}$ 的大小关系
4. 套用对应情况

递推式	$a$	$b$	$f(n)$	$n^{{\log }_{b}a}$	情况	结果
$T(n)=2T(n/2)+\mathrm{\Theta }(n)$	2	2	$\mathrm{\Theta }(n)$	$n^1=n$	2	$\mathrm{\Theta }(n\log n)$
$T(n)=2T(n/2)+\mathrm{\Theta }(1)$	2	2	$\mathrm{\Theta }(1)$	$n$	1 ($ϵ=1$)	$\mathrm{\Theta }(n)$
$T(n)=2T(n/2)+\mathrm{\Theta }(n^2)$	2	2	$\mathrm{\Theta }(n^2)$	$n$	3 ($ϵ=1$)	$\mathrm{\Theta }(n^2)$
$T(n)=4T(n/2)+\mathrm{\Theta }(n)$	4	2	$\mathrm{\Theta }(n)$	$n^2$	1 ($ϵ=1$)	$\mathrm{\Theta }(n^2)$
$T(n)=4T(n/2)+\mathrm{\Theta }(n^2)$	4	2	$\mathrm{\Theta }(n^2)$	$n^2$	2	$\mathrm{\Theta }(n^2\log n)$
$T(n)=4T(n/2)+\mathrm{\Theta }(n^3)$	4	2	$\mathrm{\Theta }(n^3)$	$n^2$	3 ($ϵ=1$)	$\mathrm{\Theta }(n^3)$
$T(n)=7T(n/3)+\mathrm{\Theta }(n^2)$	7	3	$\mathrm{\Theta }(n^2)$	$n^{{\log }_{3}7}\approx n^{1.77}$	3	$\mathrm{\Theta }(n^2)$
$T(n)=7T(n/2)+\mathrm{\Theta }(n^2)$	7	2	$\mathrm{\Theta }(n^2)$	$n^{{\log }_{2}7}\approx n^{2.81}$	1	$\mathrm{\Theta }(n^{{\log }_{2}7})$

3.2.3 主定理不能应用的情况*

当 $f(n)$ 和 $n^{{\log }_{b}a}$ 之间"差了非多项式因子"时，三种情况都不满足。

典型例子： $T(n)=2T(n/2)+\mathrm{\Theta }(n\log n)$

• $f(n)=n\log n$，$n^{{\log }_{b}a}=n$
• $f(n)$ 与 $n$ 的比较：$n\log n$ 多了一个 $\log n$ 因子
• 不满足情况 1（$n\log n\ne O(n^{1-ϵ})$）
• 不满足情况 2（$n\log n\ne \mathrm{\Theta }(n)$）
• 不满足情况 3（$n\log n\ne \mathrm{\Omega }(n^{1+ϵ})$）
• 需要使用更精细的方法（见下文主定理的推广）

为什么会"卡住"？ $f(n)=n\log n$ 比 $n$ 大，但不是多项式地大（差的是 $\log n$，不是 $n^{ϵ}$）。主定理的三种情况之间有"缝隙"，$n\log n$ 恰好落在缝隙里。

3.3 主定理的补充版本*

定理： 设 $T(n)=aT(n/b)+f(n)$，其中 $a\ge 1,b>1$。若对某个实数 $k\ge 0$：

$$f(n)=\mathrm{\Theta }(n^{{\log }_{b}a}{\log }^{k}n)$$

则：

$$T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}{\log }^{k+1}n)$$

应用： $T(n)=2T(n/2)+\mathrm{\Theta }(n\log n)$

• $n^{{\log }_{2}2}=n$，$f(n)=\mathrm{\Theta }(n{\log }^{1}n)$，$k=1$
• $T(n)=\mathrm{\Theta }(n{\log }^{2}n)$

3.4 代换法（猜测-验证）

核心思想： 先猜答案，再用数学归纳法证明。就像做数学题先算出答案，再写证明过程——猜得对，证明就顺了。

3.4.1 方法步骤

1. 猜测解的形式（来源：递归树、经验、类比）
2. 用数学归纳法证明猜测
3. 必要时减去低阶项使归纳可行（这是最常见的技巧！）

3.4.2 示例：$T(n)=2T(\lfloor n/2\rfloor )+n$

猜测： $T(n)=O(n\log n)$，即存在常数 $c$ 使得 $T(n)\le cn\log n$

归纳证明：

假设对 $m<n$，$T(m)\le cm\log m$。则：

$$T(n)=2T(\lfloor n/2\rfloor )+n\le 2c\lfloor n/2\rfloor \log \lfloor n/2\rfloor +n$$$$\le cn\log (n/2)+n=cn\log n-cn\log 2+n$$$$=cn\log n-(c\log 2-1)n$$

当 $c\ge 1/\log 2$ 时，$(c\log 2-1)n\ge 0$，因此 $T(n)\le cn\log n$ ✓

3.4.3 常见陷阱

错误做法： 猜测 $T(n)=O(n)$，归纳时：

$$T(n)=2T(n/2)+n\le 2c(n/2)+n=cn+n=(c+1)n$$

这无法证明 $T(n)\le cn$，因为 $(c+1)n>cn$。

为什么失败？ 因为 $T(n)$ 实际上是 $O(n\log n)$，猜 $O(n)$ 太小了！归纳法会诚实地告诉你——归纳过不去，说明猜测有误。

正确做法： 猜测 $T(n)\le cn\log n$，或猜测 $T(n)\le cn-dn$（减去低阶项）。

减去低阶项的技巧： 当直接猜 $T(n)\le cn$ 归纳不过时，尝试 $T(n)\le cn-dn$。多出的 $-dn$ 给了归纳一些"缓冲空间"，让不等式能够闭合。这是 CLRS 重点强调的方法。

3.5 非标准递推式的处理*

3.5.1 不同大小的子问题(下文3.6 Akra-Bazzi 方法)*

$T(n)=T(\lfloor 2n/3\rfloor )+T(\lfloor n/3\rfloor )+O(n)$

• 子问题大小不同，不能直接应用主定理
• 用递归树：每层总代价为 $O(n)$，但子问题缩小速度不均匀
• 树的深度为 $O(\log n)$（由较大的子问题 $2n/3$ 决定）
• 结果：$T(n)=O(n\log n)$

3.5.2 子问题大小相减而非相除*

$T(n)=T(n-1)+T(n-2)+O(1)$ — Fibonacci 递推

• 特征方程：$x^2=x+1$，根为 $\varphi =\frac{1+\sqrt{5}}{2}\approx 1.618$
• 解为 $T(n)=\mathrm{\Theta }({\varphi }^n)$

为什么会指数增长？ 每次分出两个子问题，但规模只减 1 和 2，树的节点数呈 Fibonacci 增长 → 指数级。和主定理的分治（规模除以 $b$，大幅缩小）截然不同。

3.6 Akra-Bazzi 方法——我们所追求的大一统之美 (内含证明)*

为什么需要 Akra-Bazzi？ 主定理只能处理 $T(n)=aT(n/b)+f(n)$ 的"整齐"分治——所有子问题大小相同。但现实中经常遇到"不整齐"的分治：

• 子问题大小不同：$T(n)=T(n/3)+T(2n/3)+f(n)$
• 子问题系数不同：$T(n)=3T(n/4)+2T(n/6)+f(n)$
• 子问题大小不是精确的 $n/b$：$T(n)=T(\lfloor n/3\rfloor )+T(\lceil 2n/3\rceil )+f(n)$

Akra-Bazzi 方法一把全收，是主定理的严格推广。

3.6.1 定理陈述*

Akra-Bazzi 定理（1998）： 设递推式形如：

$$T(x)=\{\begin{array}{ll}\mathrm{\Theta }(1)& \text{若 }1\le x\le x_0\\ {\displaystyle \sum _{i=1}^k{a}_{i}T(b_{i}x+h_i(x))+g(x)}& \text{若 }x>x_0\end{array}$$

条件：

1. $a_1,a_2,\dots ,a_k$ 为正常数（各子问题的系数）
2. $b_1,b_2,\dots ,b_k$ 为 $(0,1)$ 中的常数（各子问题的缩小比例）
3. $|h_i(x)|=O\left({\displaystyle \frac{x}{{\log }^{2}x}}\right)$（允许取整等微小偏差）
4. $g(x)$ 在 $[x_0,\mathrm{\infty })$ 上非负且满足增长条件（见下文）

定义临界值 $p$： 方程

$$\sum _{i=1}^k{a}_i{b}_i^p=1$$

的唯一正实数解 $p$。

结论：

$$T(x)=\mathrm{\Theta }\left(x^p(1+{\int }_1^x\frac{g(u)}{u^{p+1}}du)\right)$$

与主定理的对应关系：

主定理	Akra-Bazzi	说明
$a$（子问题数）	$a_1,\dots ,a_k$（各子问题系数）	主定理中 $a_1=\cdots =a_k=1$，共 $a$ 个
$n/b$（子问题大小）	$b_{1}n,\dots ,b_{k}n$（各子问题大小）	主定理中 $b_1=\cdots =b_k=1/b$
$n^{{\log }_{b}a}$（临界函数）	$n^p$，其中 $\sum a_i{b}_i^p=1$	主定理中 $\sum a_i{b}_i^p=a\cdot (1/b{)}^p=1$，解得 $p={\log }_{b}a$
$f(n)$（合并代价）	$g(x)$	同一角色

主定理是 Akra-Bazzi 在 $k=1,a_1=a,b_1=1/b$ 时的特例！

3.6.2 直觉理解*

核心直觉： Akra-Bazzi 的关键就是那个临界方程 $\sum a_i{b}_i^p=1$。

• $a_i$ 是第 $i$ 个子问题的"权重"（调了几次）
• $b_i$ 是第 $i$ 个子问题的"缩小比例"（规模变成原来的几分之几）
• $p$ 是使得"子问题总权重 × 缩小比例的 $p$ 次方"恰好平衡为 1 的指数

递归树视角： 在递归树中，第 $j$ 层有约 $\prod a_i$ 个节点，每个节点规模约 $b_i^{j}n$。临界值 $p$ 恰好是使得每层总代价的增长/衰减趋势发生转折的指数——和主定理中 ${\log }_{b}a$ 的角色完全一样。

3.6.3 使用步骤*

四步走：

1. 识别参数： 从递推式中读出 $a_i$（系数）、$b_i$（缩小比例）、$g(x)$（驱动函数）
2. 求解临界方程： 解 $\sum a_i{b}_i^p=1$ 得到 $p$
3. 计算积分： $I(x)={\int }_1^x\frac{g(u)}{u^{p+1}}du$
4. 组合结果： $T(x)=\mathrm{\Theta }(x^p(1+I(x)))$

3.6.4 应用示例*

例 1：主定理特例验证

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

• $a_1=2,b_1=1/2,g(n)=n$
• 临界方程：$2\cdot (1/2{)}^p=1$，解得 $p=1$
• 积分：${\int }_1^n\frac{u}{u^2}du={\int }_1^n\frac{1}{u}du=\ln n$
• 结果：$T(n)=\mathrm{\Theta }(n^1(1+\ln n))=\mathrm{\Theta }(n\log n)$ ✓

与主定理情况 2 完全一致！

例 2：不等大子问题

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

主定理不能用！ 因为两个子问题大小不同（$n/3$ vs $2n/3$）。

• $a_1=1,b_1=1/3$；$a_2=1,b_2=2/3$；$g(n)=n$
• 临界方程：$(1/3{)}^p+(2/3{)}^p=1$
  • $p=1$ 时：$1/3+2/3=1$ ✓，所以 $p=1$
• 积分：${\int }_1^n\frac{u}{u^2}du=\ln n$
• 结果：$T(n)=\mathrm{\Theta }(n\log n)$

递归树验证： 每层总代价约 $n$，树深约 ${\log }_{3/2}n$（由较大的 $2n/3$ 决定），总代价 $\mathrm{\Theta }(n\log n)$ ✓

例 3：不等大子问题 + 非线性驱动函数

$$T(n)=T(n/4)+T(3n/4)+n^2$$

• $a_1=1,b_1=1/4$；$a_2=1,b_2=3/4$；$g(n)=n^2$
• 临界方程：$(1/4{)}^p+(3/4{)}^p=1$
  • $p=1$ 时：$1/4+3/4=1$ ✓，所以 $p=1$
• 积分：${\int }_1^n\frac{u^2}{u^2}du={\int }_1^{n}1du=n-1$
• 结果：$T(n)=\mathrm{\Theta }(n^1(1+n))=\mathrm{\Theta }(n^2)$

例 4：多个不同系数的子问题

$$T(n)=3T(n/4)+2T(n/6)+n^2$$

• $a_1=3,b_1=1/4$；$a_2=2,b_2=1/6$；$g(n)=n^2$
• 临界方程：$3\cdot (1/4{)}^p+2\cdot (1/6{)}^p=1$
  • $p=1$ 时：$3/4+2/6=3/4+1/3=13/12>1$
  • $p=2$ 时：$3/16+2/36=3/16+1/18=27/144+8/144=35/144<1$
  • 所以 $1<p<2$（精确值需数值求解，约 $p\approx 1.17$）
• 积分：${\int }_1^n\frac{u^2}{u^{p+1}}du={\int }_1^n{u}^{1-p}du$
  • 因为 $1-p<0$（$p>1$），积分收敛到 $\mathrm{\Theta }(1)$
• 结果：$T(n)=\mathrm{\Theta }(n^p\cdot (1+1))=\mathrm{\Theta }(n^p)\approx \mathrm{\Theta }(n^{1.17})$

例 5：$\log$ 因子的情况（填补主定理的缝隙）

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

这正是主定理"卡住"的那个例子！

• $a_1=2,b_1=1/2,g(n)=n\log n$
• 临界方程：$2\cdot (1/2{)}^p=1$，$p=1$
• 积分：${\int }_1^n\frac{u\log u}{u^2}du={\int }_1^n\frac{\log u}{u}du=\frac{(\log n{)}^2}{2}$
• 结果：$T(n)=\mathrm{\Theta }(n\cdot \frac{(\log n{)}^2}{2})=\mathrm{\Theta }(n{\log }^{2}n)$

与推广主定理的结果一致！✓

3.6.5 证明方法与思路*

Akra-Bazzi 定理的证明是分析学中一个优美的论证，核心分为三步。

第一步：构造辅助函数与临界值 $p$ 的性质

定义辅助函数： $\varphi (p)=\sum _{i=1}^k{a}_i{b}_i^p$

性质分析：

• $\varphi (0)=\sum a_i\ge 1$（至少一个子问题）
• $\varphi (+\mathrm{\infty })=0$（$b_i\in (0,1)$，$b_i^p\to 0$）
• ${\varphi }^{\prime }(p)=\sum a_i{b}_i^p\ln b_i<0$（$\ln b_i<0$）
• 因此 $\varphi$ 严格递减，从 $\ge 1$ 递减到 $0$

由介值定理，存在唯一 $p>0$ 使得 $\varphi (p)=1$，即 $\sum a_i{b}_i^p=1$。

$p$ 的含义： $p$ 是递归树中"每层总代价增长率"的转折点。$n^p$ 刻画了叶子节点总工作量。

第二步：构造特解——积分变换法

核心构造： 定义

$$\hat{T}(x)=x^p(1+{\int }_1^x\frac{g(u)}{u^{p+1}}du)$$

验证 $\hat{T}$ 近似满足递推式：

需要证明 $\hat{T}(x)\approx \sum a_i\hat{T}(b_{i}x)+g(x)$。

关键计算：

$$\sum _{i=1}^k{a}_i\hat{T}(b_{i}x)=\sum _{i=1}^k{a}_i(b_{i}x{)}^p(1+{\int }_1^{b_{i}x}\frac{g(u)}{u^{p+1}}du)$$$$=x^p\sum _{i=1}^k{a}_i{b}_i^p(1+{\int }_1^{b_{i}x}\frac{g(u)}{u^{p+1}}du)$$

利用 $\sum a_i{b}_i^p=1$ 和积分区间的拆分：

$${\int }_1^x\frac{g(u)}{u^{p+1}}du=\sum _{i=1}^k{a}_i{b}_i^p{\int }_1^x\frac{g(u)}{u^{p+1}}du$$

通过变量替换 $u=b_{i}v$：

$$a_i{b}_i^p{\int }_1^x\frac{g(u)}{u^{p+1}}du=a_i{\int }_{1/b_i}^{x/b_i}\frac{g(b_{i}v)}{v^{p+1}}dv$$$$\approx a_i{\int }_1^{b_{i}x}\frac{g(u)}{u^{p+1}}du$$

（此处利用了 $h_i(x)=O(x/{\log }^{2}x)$ 的条件，保证取整偏差不影响积分值。）

最终得到：

$$\hat{T}(x)-\sum a_i\hat{T}(b_{i}x)=x^p\cdot \frac{g(x)}{x^{p+1}}\cdot x+\text{低阶项}\approx g(x)$$

这验证了 $\hat{T}$ 确实近似满足递推式。

第三步：上下界夹逼（$\mathrm{\Theta }$ 证明）

上界证明（$T(x)=O(\hat{T}(x))$）：

构造 $U(x)=C\cdot \hat{T}(x)$，选择足够大的常数 $C$ 使得：

• 基础情况：对所有 $x\le x_0$，$T(x)\le U(x)$
• 归纳步：假设对 $y<x$，$T(y)\le U(y)$，则

$$T(x)=\sum a_{i}T(b_{i}x+h_i(x))+g(x)\le \sum a_{i}U(b_{i}x+h_i(x))+g(x)$$

利用 $h_i(x)$ 的微小性和 $\hat{T}$ 的连续性，可证 $\le U(x)$。

下界证明（$T(x)=\mathrm{\Omega }(\hat{T}(x))$）： 完全对称，构造 $L(x)=c\cdot \hat{T}(x)$，选择足够小的 $c$。

合起来： $L(x)\le T(x)\le U(x)$，即 $T(x)=\mathrm{\Theta }(\hat{T}(x))$。 $◼$

证明的核心洞见：

1. 临界方程 $\sum a_i{b}_i^p=1$ 不是凭空来的——它来自要求"特解 $\hat{T}(x)=x^p\cdot (\cdots )$ 代入递推式后，$x^p$ 的系数恰好平衡"
2. 积分不是凭空来的——它来自对递归树逐层求和后的连续化近似。递归树每层代价约 $g(n/b^j)$，求和 $\sum _{j}g(n/b^j)$ 用积分 $\int g(u)/u^{p+1}du$ 近似
3. $h_i(x)$ 的条件保证了取整不影响——$O(x/{\log }^{2}x)$ 的偏差在积分中是"可忽略的"，这就是为什么 $\lfloor n/2\rfloor$ 和 $n/2$ 在渐进分析中等价

• Akra-Bazzi 是主定理的严格推广，会 Akra-Bazzi 就会主定理

---

第四部分：空间复杂度分析

逝者如斯，时间是一去不返的——每个操作花费的时间都会累加；但是空间是物质存在的，用完即还的——函数返回后，栈帧被弹出，内存被回收。因此：

• 时间复杂度看递归树的所有节点总代价
• 空间复杂度看递归树的根到叶最长路径上的代价

4.1 空间复杂度的定义

4.1.1 形式化定义

定义： 算法的空间复杂度 $S(n)$ 是算法在输入规模为 $n$ 时所消耗的额外存储空间（不包括输入本身）的渐进量度：

$$S(n)=\text{算法运行过程中任意时刻占用的最大额外内存}$$

"额外"的含义： 我们只算算法自己申请的内存，不算输入数据占用的空间。这叫"辅助空间"（auxiliary space）。如果算上输入，那所有算法至少都是 $\mathrm{\Omega }(n)$，何意味。

4.1.2 与时间复杂度的根本区别

维度	时间复杂度	空间复杂度
累积方式	加法：所有操作时间累加	最大值：取任意时刻的峰值
递归树含义	所有节点的代价之和	根到叶最长路径上的代价之和
释放/回收	时间不可回收	空间可以回收（函数返回后释放）
子问题并行	并行子问题时间可重叠	并行子问题空间不重叠（各占各的）
子问题串行	串行子问题时间累加	串行子问题空间可复用

4.2 空间消耗的三大来源

4.2.1 栈空间——递归算法的主要空间消耗

每次递归调用，系统在调用栈上压入一个栈帧（Stack Frame），包含：

• 返回地址
• 函数参数
• 局部变量
• 保存的寄存器值

栈帧大小： 对于简单递归函数（参数和局部变量都是基本类型），每层栈帧大小为 $O(1)$。如果参数中传了大数组（值传递），栈帧可能为 $O(n)$。

关键性质： 栈帧在函数返回时弹出释放。因此在任意时刻，栈中只存在从 main 到当前正在执行的函数这条调用链上的栈帧。

main() → f(10) → f(7) → f(4) → f(1)  ← 当前正在执行
           ↑        ↑        ↑        ↑
         栈帧存在   栈帧存在  栈帧存在  栈帧存在
         
f(10) 的其他子调用 f(3) 已经返回，栈帧已释放！

结论： 递归算法的栈空间 = 递归深度 × 每层栈帧大小

4.2.2 堆空间——显式申请的额外数据结构

算法中通过 malloc、new、数组声明等方式在堆上分配的内存：

操作	空间消耗	说明
int* aux = new int[n]	$O(n)$	归并排序的辅助数组
vector<int> path 逐步 push	最多 $O(n)$	DFS 的路径数组
HashMap<K,V> map 插入 $n$ 个	$O(n)$	图遍历的 visited 集合
int temp	$O(1)$	单个临时变量

堆空间的释放时机： 如果辅助数组是在递归函数内部声明的局部变量，函数返回后自动释放。如果在递归前只申请一次（如归并排序的 aux 数组），则全程占用。

4.2.3 输入空间——通常不计

输入数据本身占用的空间通常不计入空间复杂度，原因：

• 输入是"给定的"，算法无法控制
• 如果计入，所有算法至少 $\mathrm{\Omega }(n)$，无法区分
• 我们关注的是算法额外需要的空间

例外： 如果算法修改了输入数据并以此作为额外存储（如原地算法在输入数组上做标记），这种"借用"的空间可以算作 $O(1)$ 额外空间。

4.3 空间复杂度的核心分析原则

核心公式：

$$\begin{gathered} S(n)=\underset{\text{栈空间}}{\underbrace{\text{递归最大深度}\times \text{每层栈帧大小}}} \\ +\underset{\text{堆空间}}{\underbrace{\text{堆上同时存在的最大数据量}}} \end{gathered}$$

4.3.1 递归算法的空间分析——"看树的最长路径"

递归树视角：

• 时间：递归树所有节点的代价之和（因为每个节点都要执行）
• 空间：递归树从根到叶最长路径上的代价之和（因为同一时刻只有一条路径上的栈帧存在）

这就是空间分析的黄金法则：盯住最长路径，忽略兄弟节点！

具体步骤：

1. 确定递归树的最大深度 $d(n)$
2. 确定每层栈帧的大小 $frame(n)$
3. 确定算法申请的堆空间 $heap(n)$
4. 组合：$S(n)=d(n)\times frame(n)+heap(n)$

4.3.2 非递归算法的空间分析——"盯住最大分配"

对于没有递归的迭代算法：

• 没有栈增长的问题
• 空间 = 所有同时存在的变量/数据结构占用的内存之和

"同时存在"是关键： 如果两个数组分别在 if 的两个分支中创建，它们不会同时存在，空间取 max 而非 sum。

4.4 实战：从代码到空间复杂度

例 1：递归二分查找

int binarySearch(int* arr, int lo, int hi, int target) {
    if (lo > hi) return -1;
    int mid = (lo + hi) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] > target) 
        return binarySearch(arr, lo, mid-1, target);  // 只走一条路！
    else
        return binarySearch(arr, mid+1, hi, target);
}

• 递归深度：每次规模减半 → $O(\log n)$
• 每层栈帧：参数 lo, hi, target + 局部变量 mid → $O(1)$
• 堆空间：无
• 结果：$S(n)=O(\log n)$

递归树： 每个节点只有一个子节点（只走一条路），树是一条链，深度 $\log n$。

例 2：归并排序

void mergeSort(int* arr, int lo, int hi) {
    if (lo >= hi) return;
    int mid = (lo + hi) / 2;
    mergeSort(arr, lo, mid);      // 先排左半
    mergeSort(arr, mid+1, hi);    // 再排右半
    merge(arr, lo, mid, hi);      // 合并（需要辅助数组）
}

• 递归深度：$O(\log n)$
• 每层栈帧：$O(1)$（只传指针和索引）
• 堆空间：merge 中申请辅助数组 $O(n)$（如果在外部一次性申请则全程占 $O(n)$）
• 结果：$S(n)=O(n)$（堆空间主导）

常见错误： 认为"每层递归都申请 $O(n)$ 辅助数组，共 $\log n$ 层，所以 $O(n\log n)$"。

纠正： 辅助数组通常在 merge 函数内局部申请，merge 结束后释放。在任意时刻，只有当前正在 merge 的那一层占用 $O(n)$，所以堆空间就是 $O(n)$。

例 3：递归斐波那契

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

• 时间复杂度：$O(2^n)$（递归树节点总数）
• 递归深度：$O(n)$（最深的路径是 $n\to n-1\to n-2\to \cdots \to 1$）
• 每层栈帧：$O(1)$
• 空间复杂度：$S(n)=O(n)$

反直觉： 时间是指数级，空间是线性级！这就是"空间只看深度"的威力——递归树虽然庞大，但同一时刻只有一条路径上的栈帧存在。

例 4：快速排序

void quickSort(int* arr, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = partition(arr, lo, hi);
    quickSort(arr, lo, pivot-1);    // 先排左半
    quickSort(arr, pivot+1, hi);    // 再排右半
}

• 最坏情况（已排序数组）：pivot 总是取到端点，退化为链
  • 递归深度：$O(n)$ → $S(n)=O(n)$（可能栈溢出！）
• 最好/平均情况：pivot 接近中位数
  • 递归深度：$O(\log n)$ → $S(n)=O(\log n)$
• 堆空间：partition 是原地操作，$O(1)$

递归深度优化： 始终先递归较小的半边，较大半边用循环，可以保证深度 $O(\log n)$：

void quickSort(int* arr, int lo, int hi) {
    while (lo < hi) {
        int p = partition(arr, lo, hi);
        if (p - lo < hi - p) {
            quickSort(arr, lo, p-1);   // 递归小的半边
            lo = p + 1;                 // 大的半边用循环
        } else {
            quickSort(arr, p+1, hi);
            hi = p - 1;
        }
    }
}

例 5：DFS 图遍历

void dfs(int node, bool* visited) {
    visited[node] = true;
    for (int neighbor : adj[node]) {
        if (!visited[neighbor])
            dfs(neighbor, visited);
    }
}

• 递归深度：取决于图的结构
  • 链状图：$O(n)$
  • 平衡树：$O(\log n)$
  • 一般图：$O(n)$（最坏）
• 堆空间：visited 数组 $O(n)$ + 递归隐含的路径栈
• 结果：$S(n)=O(n)$（visited 数组 + 最坏递归深度）

例 6：动态规划——空间优化

二维 DP（未优化）：

int dp[n+1][m+1];   // O(nm) 空间
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        dp[i][j] = dp[i-1][j] + dp[i][j-1];

滚动数组优化：

int dp[2][m+1];     // O(m) 空间！
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        dp[i%2][j] = dp[(i-1)%2][j] + dp[i%2][j-1];

核心思想： 如果 dp[i][j] 只依赖前一行 dp[i-1][*] 和当前行 dp[i][*]，那只需保留两行。空间从 $O(nm)$ 降到 $O(m)$。

一维优化（如果只依赖左边和上方）：

int dp[m+1];        // O(m) 空间！
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        dp[j] = dp[j] + dp[j-1];   // 覆盖旧值

4.5 递推法分析空间——类比主定理

核心思想： 空间递推式和时间的关键区别——子问题个数 $a$ 不乘！

4.5.1 为什么空间递推不乘 $a$？

对于时间递推 $T(n)=aT(n/b)+f(n)$，子问题是依次执行的（不是同时）。空间可以复用——第一个子问题算完释放空间，第二个子问题可以复用同一片内存。所以堆空间不乘 $a$，只看一条路径的深度。

但要注意，空间有两种，递推式不一样：

• 栈空间沿递归深度累加（每层一个栈帧，从根到叶子同时存在）：$$S_{\mathrm{栈}}(n)=S_{\mathrm{栈}}(n/b)+O(1)$$
• 堆空间子问题复用，取峰值：$$S_{\mathrm{堆}}(n)=max(S_{\mathrm{堆}}(n/b),\text{当前层辅助空间})$$

一句话：栈空间加法，堆空间取 max。这正是 4.3 节「空间看树的最长路径」的递推形式。

4.5.2 递推求解示例

归并排序：

• 栈空间：递归深度 $O(\log n)$，每层栈帧 $O(1)$ → $O(\log n)$
• 堆空间：merge 的辅助数组 $O(n)$，子问题依次执行、空间复用，峰值就是 $O(n)$
• 合计：$S(n)=O(\log n)+O(n)=O(n)$（堆空间主导）

二分查找：

• 栈空间：递归深度 $O(\log n)$，每层栈帧 $O(1)$ → $O(\log n)$
• 堆空间：无
• 合计：$S(n)=O(\log n)$

快速排序（最坏）：

• 栈空间：已有序时退化成链，深度 $O(n)$，每层 $O(1)$ → $O(n)$
• 堆空间：partition 原地，$O(1)$
• 合计：$S(n)=O(n)$

Karatsuba 大整数乘法：

时间：$T(n)=3T(n/2)+O(n)=O(n^{{\log }_{2}3})$

空间：栈 $O(\log n)$ + 辅助数组 $O(n)$ = $O(n)$（虽然时间有 3 个子问题，空间只走 1 条路）

4.5.3 通用公式

对于分治递推 $T(n)=aT(n/b)+f(n)$ 的空间复杂度，拆成两部分：

• 栈空间：$S_{\mathrm{栈}}(n)=O(1)\times d$，其中 $d$ 是递归深度
• 堆空间：$S_{\mathrm{堆}}(n)=\underset{i}{max}\left\{\text{第 }i\text{ 层同时存在的辅助空间}\right\}$

合计 $S(n)=S_{\mathrm{栈}}(n)+S_{\mathrm{堆}}(n)$。多数时候二者其一占主导，取较大者即可。

常见情况速查：

每层额外空间	递归深度	空间复杂度	例子
$O(1)$	$O(\log n)$	$O(\log n)$	二分查找、堆操作
$O(1)$	$O(n)$	$O(n)$	递归斐波那契、最坏快排
$O(n)$	$O(\log n)$	$O(n)$	归并排序、Karatsuba
$O(n)$	$O(n)$	$O(n^2)$	递归中每层拷贝数组

4.6 原地算法（In-place Algorithm）*

4.6.1 严格定义*

定义： 如果算法的辅助空间（不包括输入和输出）为 $O(1)$，则称其为原地算法。

4.6.2 常见算法的原地性分类*

算法	辅助空间	是否原地	说明
冒泡排序	$O(1)$	✅ 严格原地	只需一个 temp 变量
插入排序	$O(1)$	✅ 严格原地	只需一个 key 变量
堆排序	$O(1)$	✅ 严格原地	在原数组上建堆
快速排序	$O(\log n)$	❌ 非严格原地	递归栈空间
归并排序	$O(n)$	❌ 非原地	辅助数组
计数排序	$O(n+k)$	❌ 非原地	计数数组 + 输出数组
基数排序	$O(n+k)$	❌ 非原地	桶空间

关于快排： 快排的 $O(\log n)$ 栈空间通常被认为"近似原地"，因为 $\log n$ 在实践中很小（$n={10}^6$ 时 $\log n\approx 20$）。但严格数学定义上，$O(\log n)\ne O(1)$，所以快排不是原地算法。

4.6.3 原地算法的设计技巧*

技巧	说明	例子
交换操作	用 temp 或 XOR 交换，不需要额外数组	快排的 partition
原地反转	首尾指针向中间交换	反转字符串
位运算压缩	用输入数据的空闲位存额外信息	原地哈希标记
输入做输出	在输入数组上直接修改	堆排序、快排
双指针	两个指针在原数组上移动	原地去重、荷兰国旗问题

4.7 空间复杂度常见陷阱

陷阱	错误分析	正确分析
混淆时间和空间	认为时间 $O(2^n)$ 则空间也是 $O(2^n)$	空间只看深度，斐波那契空间 $O(n)$
每层递归都算堆空间	"归并每层都申请 $O(n)$，共 $O(n\log n)$"	辅助数组用完即释放，同一时刻只有一层占 $O(n)$
忽略递归栈	只算堆空间，忘了递归本身也占栈	递归深度 × 栈帧大小
传值拷贝数组	每层递归拷贝整个数组	传引用/指针只占 $O(1)$，传值每层 $O(n)$
DP 不优化空间	直接开 $O(nm)$ 二维数组	滚动数组可降到 $O(m)$
认为快排是原地的	$O(\log n)$ 不等于 $O(1)$	严格来说快排不是原地算法

空间分析的核心口诀： 时间加总，空间看峰；递归看深，堆看最大。

4.8 时间与空间的权衡（Time-Space Tradeoff）*

核心思想： 时间和空间往往不可兼得——用空间换时间，或用时间换空间。

4.8.1 经典权衡案例*

权衡方向	例子	额外空间	时间收益
空间换时间	哈希表 vs 线性查找	$O(n)$ 额外空间	查找从 $O(n)$ → $O(1)$
空间换时间	记忆化递归（fib）	$O(n)$ 备忘录	从 $O(2^n)$ → $O(n)$
空间换时间	预计算前缀和	$O(n)$ 前缀数组	区间和从 $O(n)$ → $O(1)$
时间换空间	原地反转 vs 拷贝反转	$O(1)$ vs $O(n)$	时间都是 $O(n)$，但原地不用额外空间
时间换空间	位运算代替数组	$O(1)$ 位图	位操作略慢于数组索引
空间换时间	B树 vs 二叉搜索树	B树节点更大	减少磁盘 I/O（更浅的树）

4.8.2 记忆化的空间分析*

普通递归斐波那契： 时间 $O(2^n)$，空间 $O(n)$

记忆化斐波那契：

int memo[MAX];  // O(n) 额外空间
int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];  // 查表
    return memo[n] = fib(n-1) + fib(n-2);
}

• 时间：$O(n)$（每个值只算一次）
• 空间：$O(n)$（memo 数组 + 递归深度 $O(n)$）
• 权衡：用 $O(n)$ 空间，把时间从 $O(2^n)$ 降到 $O(n)$

4.8.3 递归 vs 迭代的空间对比*

算法	递归实现空间	迭代实现空间	说明
二分查找	$O(\log n)$	$O(1)$	迭代消除递归栈
归并排序	$O(n+\log n)$	$O(n)$	迭代版（自底向上）省了栈
快速排序	$O(\log n)$	$O(\log n)$	用显式栈模拟，空间不变
DFS	$O(h)$	$O(h)$	用显式栈模拟，空间不变
斐波那契	$O(n)$	$O(1)$	迭代只需两个变量

消除递归的通用方法： 用显式栈模拟递归调用。空间上通常不会更优（栈还是要用的），但可以避免系统栈溢出。某些情况下（如尾递归），可以完全消除栈。

4.9 特殊空间概念*

4.9.1 输入空间 vs 辅助空间*

• 输入空间： 存储输入数据所需的空间。对于 $n$ 个元素的数组，输入空间为 $\mathrm{\Theta }(n)$。
• 辅助空间： 算法额外申请的空间，$S_{aux}(n)=S_{total}(n)-S_{input}(n)$。
• 空间复杂度通常指辅助空间。

4.9.2 输出空间*

如果算法的输出规模与输入不同（如排列生成所有 $n!$ 个排列），输出空间需要单独考虑。通常不计入空间复杂度，但某些问题（如流式算法）输出空间是瓶颈。

4.9.3 工作空间（Work Space）*

定义： 工作空间 = 辅助空间中，在算法运行过程中只读部分之外的空间。

对于原地算法，工作空间 = $O(1)$。

4.9.4 空间层次定理*

Savitch 定理（1970）： 对于任何 $S(n)\ge \log n$ 的空间可构造函数：

$$\text{NSPACE}(S(n))\subseteq \text{DSPACE}(S^2(n))$$

即非确定性空间 $S(n)$ 可以被确定性空间 $S^2(n)$ 模拟。

例子： 如果一个问题用非确定性算法在 $O(n)$ 空间可解，则用确定性算法在 $O(n^2)$ 空间可解。

与时间层次的对比： 时间的类似模拟需要指数级增长（$\text{NP}\subseteq \text{EXPTIME}$），而空间只需平方级。这说明空间比时间更"强"——空间可以复用，时间不行。

4.10 常见数据结构的空间复杂度速查

数据结构	存储空间	说明
数组 int arr[n]	$O(n)$	连续存储
链表（$n$ 个节点）	$O(n)$	每个节点还要存指针
二叉树（$n$ 个节点）	$O(n)$	每个节点 2 个指针
哈希表（$n$ 个元素）	$O(n)$	平均负载因子 < 1
栈/队列（$n$ 个元素）	$O(n)$
堆（$n$ 个元素）	$O(n)$	数组实现
图——邻接矩阵	$O(V^2)$	稠密图
图——邻接表	$O(V+E)$	稀疏图
并查集	$O(n)$	parent + rank 数组
字典树（Trie）	$O(n\times L)$	$n$ 个串，平均长 $L$
线段树	$O(n)$	通常开 $4n$
树状数组（BIT）	$O(n)$

---

相信看完上述倾情讲述的内容读者对时间复杂度与空间复杂度有了大概的概念，在接下来的具体数据结构与算法中，我们会大量运用本章概述的内容，希望对以后的学习有所帮助喵