(7) 递归算法 -2 复杂度分析

GESP C++五级官方考试大纲中，共有9条考点，本文针对第7条考点进行分析介绍。

Important

（7）掌握递归算法的基本原理，能够应用递归解决问题，能够分析递归算法的时间复杂度和空间复杂度，了解递归的优化策略。

Warning

本人也是边学、边实验、边总结，且对考纲深度和广度的把握属于个人理解。因此本文更多的不是一个教程，而是个人知识梳理，如有遗漏、疏忽，欢迎指正、交流。

五级其他考点回顾：

Tip

在梳理的过程中，我发现想尽可能说清楚考纲要求的内容，越总结篇幅越长，为了避免总结遗漏和阅读匹配，我计算分三次介绍本部分内容，即：
递归算法基本原理和常见形式
递归算法时间、空间复杂度分析
递归算法优化策略
本次为第二部分介绍。

递归算法因代码简洁、逻辑直观，成为解决分治、回溯类问题的常用工具，但“层层调用”的特性也让其时间复杂度分析比迭代算法更复杂。

一、时间复杂度分析

1.1 递归时间复杂度分析的本质：看调用次数 × 每次工作量

递归算法的运行时间，取决于递归调用的次数和每次调用要干的活。

换句话说，我们要搞清楚：

递归函数会被调用多少次？
每次调用花多长时间？

只要能回答这两个问题，复杂度就能算出来。

1.2 三步通用分析法

我们通常用下面 三步法 来分析递归复杂度：

第 1 步：写出递归式

假设递归问题规模是 n，那么写出：

T(n) = a \times T(n/b) + f(n)

意思是：

把问题拆成 $a$ 个子问题；
每个子问题规模是原来的 $n/b$ ；
拆分和合并需要 $f(n)$ 的时间。

第 2 步：分析子问题的增长规律

看递归树怎么展开，越往下子问题越多、越小。

第 3 步：求出总和（用递归树法或主定理）

算出整棵递归树所有节点的总工作量。下面分别介绍这两种方法。

1.3 递归树法（最直观的理解方式）

递归树法其实就是「画一棵树」来看递归展开过程，例如：👇

示例 1：二分查找

// 二分查找：在有序数组 arr[left...right] 中查找目标值 target
int binarySearch(int arr[], int left, int right, int target) {
    // 如果区间无效，说明未找到，返回 -1
    if (left > right) {
        return -1;
    }
    int mid = (left + right) / 2; // 计算中间位置
    if (arr[mid] == target) {
        return mid; // 找到目标，返回下标
    } else if (arr[mid] > target) {
        // 目标在左半部分，递归查找左区间
        return binarySearch(arr, left, mid - 1, target);
    } else {
        // 目标在右半部分，递归查找右区间
        return binarySearch(arr, mid + 1, right, target);
    }
}

分析：

每次只递归一次（ $a = 1$ ）
规模减半（ $b = 2$ ）
其他操作 $O(1)$

写出递归式：

T(n) = T(n/2) + O(1)

画成树后你会发现，深度是 $\log_2n$ ，每层只干一点活：

T(n) = O(\log n)

示例 2：归并排序

void mergeSort(int arr[], int l, int r) {
    // 区间长度 ≤ 1 时已经有序，直接返回
    if (l >= r) {
        return;
    }
    // 取中点，将区间一分为二
    int mid = (l + r) / 2;
    // 递归排序左半部分 [l, mid]
    mergeSort(arr, l, mid);
    // 递归排序右半部分 [mid+1, r]
    mergeSort(arr, mid + 1, r);
    // 合并两个已排序的子区间
    merge(arr, l, mid, r);
}

分析：

拆成两个子问题（ $a = 2$ ）
每个子问题规模一半（ $b = 2$ ）
合并需要 $O(n)$ 时间

递归式：

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

画成树：

第 0 层：1 个节点，工作量 $n$
第 1 层：2 个节点，总工作量 $n$
第 2 层：4 个节点，总工作量 $n$
……
一共有 $O(\log_2 n)$ 层

总时间：

T(n) = O(n \log n)

1.4 主定理（Master Theorem）

当我们懒得画树时，可以直接用主定理。

对于递归式：

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

主定理告诉我们：

情况	规律	复杂度
1️⃣ 子问题主导	若 $f(n) = O(n^{\log_b a - \epsilon})$	$T(n) = \Theta(n^{\log_b a})$
2️⃣ 平衡	若 $f(n) = \Theta(n^{\log_b a})$	$T(n) = \Theta(n^{\log_b a} \log n)$
3️⃣ 合并主导	若 $f(n) = \Omega(n^{\log_b a + \epsilon})$ 且满足正则性条件*	$T(n) = \Theta(f(n))$

Tip

注：正则性条件说明

正则性条件：存在常数 $c<1$ 使得对所有足够大的 $n$ 有 $a f(n/b) \le c f(n)$ ，确保“上层合并不吃掉下层优势”。

举几个典型例子：

递归式	主定理判定过程	复杂度	例子
$T(n) = 2T(n/2) + O(n)$	$n^{\log_b a}=n^1$ ， $f(n)=O(n)$ 恰好相等 → 情况2️⃣ 平衡	$O(n \log n)$	归并排序
$T(n) = T(n/2) + O(1)$	$n^{\log_b a}=n^0=1$ ， $f(n)=O(1)$ 恰好相等 → 情况2️⃣ 平衡	$O(\log n)$	二分查找
$T(n) = 4T(n/2) + O(n^2)$	$n^{\log_b a}=n^2$ ， $f(n)=O(n^2)$ 恰好相等 → 情况2️⃣ 平衡	$O(n^2 \log n)$	四分递归（例如图像分割）
$T(n) = 9T(n/3) + O(n)$	$n^{\log_b a}=n^2$ ， $f(n)=O(n)=O(n^{2-1})$ 多项式小于 → 情况1️⃣ 子问题主导	$O(n^2)$	分治矩阵乘法（朴素法）
$T(n) = 2T(n/2) + O(n^2)$	$n^{\log_b a}=n^1$ ， $f(n)=O(n^2)$ 多项式大于 → 情况3️⃣ 合并主导	$O(n^2)$	暴力合并的区间问题

1.5 小结

技巧/误区	说明
✅ 常数项不影响复杂度	只看数量级
✅ 画递归树最直观	适合新手理解结构
⚠️ 不要只看递归次数	每层的「工作量」常常不同
⚠️ 要区分尾递归和非尾递归	尾递归能优化空间，但不改变时间复杂度

二、空间复杂度分析

空间复杂度描述的是：

Note

算法在运行过程中额外占用的内存空间量，与输入规模 $n$ 的关系。

“额外”指的是不算输入数据本身，只算程序执行中自己用到的额外内存，例如：

临时变量；
函数调用栈；
临时数组或缓冲区。

1.1 递归为什么会占用空间

因为每一次函数调用，计算机都会在**调用栈（call stack）**里存放一份当前函数的信息：

参数值；
局部变量；
返回地址。

当函数自己调用自己时，会再压入一层栈帧。

比如你写：

void f(int n) {
    if (n == 0) return;
    f(n - 1);
}

每次 f(n) 调用 f(n-1) 时，系统会新建一个“函数栈帧”。直到递归到底（n==0）才开始弹栈。

所以：

栈的深度 = 递归的层数；
每一层栈帧占一定空间；

因此：

Note

递归的空间复杂度 = 递归调用的最大深度 × 每次调用占用的空间。

通常，每次调用的局部变量数量是常数级的，所以空间复杂度主要看递归深度。

1.2 举例子分析

例1：简单线性递归

void f(int n) {
    if (n == 0) return;
    f(n - 1);
}

最大调用深度： $n$
每次只用常数空间（比如局部变量 $n$ ）

✅ 空间复杂度： $O(n)$

例2：二叉递归

void f(int n) {
    if (n == 0) return;
    f(n - 1);
    f(n - 1);
}

你可能以为是 $O(2^n)$ ，其实不是！

空间不是时间。虽然函数被调用了很多次，但它们不是同时存在的，因为每次左子递归返回后，才开始右子递归。

递归深度仍是 $n$ ；
所以栈深度也就是 $n$ 层

✅ 空间复杂度仍是 $O(n)$ 。

例3：分治算法（如归并排序）

void mergeSort(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);
    merge(l, mid, r); // 合并
}

递归深度是 $O(\log n)$ （每次一分为二）。
但合并时可能用一个临时数组来存结果，这个临时数组大小为 $O(n)$ 。

所以：

栈空间： $O(\log n)$
额外数组： $O(n)$

✅ 总空间复杂度： $O(n)$ （取最大者）

例4：尾递归优化（特殊情况）

void tail(int n, int acc) {
    if (n == 0) return;
    tail(n - 1, acc + n);
}

如果编译器支持尾递归优化（TCO），系统就不会真的创建新的栈帧，而是重用当前函数的空间。 ✅ 空间复杂度从 $O(n)$ 降到 $O(1)$ 。

（但 C++ 默认不保证 TCO，一般仍是 $O(n)$ ）

1.3 小结

1️⃣ 确定递归的最大深度（最深能调用多少层）。
2️⃣ 看每层使用了多少局部空间（常量？数组？）。
3️⃣ 判断是否有额外辅助结构（比如合并时的临时数组）。
4️⃣ 计算总空间 = 栈空间 + 辅助空间。
5️⃣ 忽略常数项，取最大阶，写成 O(·) 表达。

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号

最后更新于 2025年10月13日

(7) 递归算法 - 1 基本原理 (7) 递归算法 -3 优化策略