OneCoder Avatar
OneCodercoderli.com · 1025 篇博文
五级

C++ 算法考级专栏

🎨 视觉封面

【GESP】C++五级考试大纲知识点梳理, (7) 递归算法 -2 复杂度分析

📅 2025-10-09·✍️ OneCoder·计算中...·⏱️ 16 分钟

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

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

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

五级其他考点回顾:


在梳理的过程中,我发现想尽可能说清楚考纲要求的内容,越总结篇幅越长,为了避免总结遗漏和阅读匹配,我计算分三次介绍本部分内容,即:

  1. 递归算法基本原理和常见形式
  2. 递归算法时间、空间复杂度分析
  3. 递归算法优化策略

本次为第二部分介绍。

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


一、时间复杂度分析

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

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

换句话说,我们要搞清楚:

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

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


1.2 三步通用分析法

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

第 1 步:写出递归式

假设递归问题规模是 n,那么写出:

意思是:

  • 把问题拆成 个 子问题;
  • 每个子问题规模是原来的 ;
  • 拆分和合并需要 的时间。

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

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

第 3 步:求出总和(用递归树法或主定理)

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


1.3 递归树法(最直观的理解方式)

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

示例 1:二分查找

C++17 行
// 二分查找:在有序数组 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);
    }
}

分析:

  • 每次只递归一次()
  • 规模减半()
  • 其他操作

写出递归式:

画成树后你会发现,深度是 ,每层只干一点活:


示例 2:归并排序

C++14 行
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);
}

分析:

  • 拆成两个子问题()
  • 每个子问题规模一半()
  • 合并需要 时间

递归式:

画成树:

  • 第 0 层:1 个节点,工作量
  • 第 1 层:2 个节点,总工作量
  • 第 2 层:4 个节点,总工作量
  • ……
  • 一共有 层

总时间:


1.4 主定理(Master Theorem)

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

对于递归式:

主定理告诉我们:

情况 规律 复杂度
1️⃣ 子问题主导 若
2️⃣ 平衡 若
3️⃣ 合并主导 若 且满足正则性条件*

注:正则性条件说明

正则性条件:存在常数 使得对所有足够大的 有 ,确保“上层合并不吃掉下层优势”。

举几个典型例子:

递归式 主定理判定过程 复杂度 例子
, 恰好相等 → 情况2️⃣ 平衡 归并排序
, 恰好相等 → 情况2️⃣ 平衡 二分查找
, 恰好相等 → 情况2️⃣ 平衡 四分递归(例如图像分割)
, 多项式小于 → 情况1️⃣ 子问题主导 分治矩阵乘法(朴素法)
, 多项式大于 → 情况3️⃣ 合并主导 暴力合并的区间问题

1.5 小结

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

二、空间复杂度分析

空间复杂度描述的是:

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

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

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

1.1 递归为什么会占用空间

因为每一次函数调用,计算机都会在**调用栈(call stack)**里存放一份当前函数的信息:

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

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

比如你写:

C++4 行
void f(int n) {
    if (n == 0) return;
    f(n - 1);
}

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

所以:

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

因此:

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

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


1.2 举例子分析

例1:简单线性递归

C++4 行
void f(int n) {
    if (n == 0) return;
    f(n - 1);
}
  • 最大调用深度:
  • 每次只用常数空间(比如局部变量 )

✅ 空间复杂度:


例2:二叉递归

C++5 行
void f(int n) {
    if (n == 0) return;
    f(n - 1);
    f(n - 1);
}

你可能以为是 ,其实不是!

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

  • 递归深度仍是 ;
  • 所以栈深度也就是 层

✅ 空间复杂度仍是 。


例3:分治算法(如归并排序)

C++7 行
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); // 合并
}
  • 递归深度是 (每次一分为二)。
  • 但合并时可能用一个临时数组来存结果,这个临时数组大小为 。

所以:

  • 栈空间:
  • 额外数组:

✅ 总空间复杂度:(取最大者)


例4:尾递归优化(特殊情况)

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

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

(但 C++ 默认不保证 TCO,一般仍是 )


1.3 小结

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


看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

GESP 编程与算法 · 五级⏱️ 11 分钟

【GESP】C++五级考试大纲知识点梳理, (1) 初等数论

GESP C++五级官方考试大纲中,共有9条考点,本文针对第1条考点进行分析介绍。 (1)掌握初等数论相关知识的概念和应用,包括素数与合数、最大公约数与最小公倍数、同余与模运算、约数与倍数、质因数分解、奇偶性等。 由于本人也是边学、边实验、边总结,且对考纲深度和广度的把...

阅读全文 →
GESP 编程与算法 · 五级⏱️ 31 分钟

【GESP】C++五级考试大纲知识点梳理, (2) 模拟高精度计算

GESP C++五级官方考试大纲中,共有9条考点,本文针对第2条考点进行分析介绍。 (2)掌握 C++数组模拟高精度加法、减法、乘法和除法的相关知识。 五级其他考点回顾: - 【GESP】C++五级考试大纲知识点梳理, (1) 初等数论 由于本人也是边学、边实验、边总结...

阅读全文 →
GESP 编程与算法 · 五级⏱️ 19 分钟

【GESP】C++五级考试大纲知识点梳理, (3-1) 链表-单链表

GESP C++五级官方考试大纲中,共有9条考点,本文针对第3条考点进行分析介绍。 (3)掌握链表的创建、插入、删除、遍历和反转操作,理解单链表、双链表、循环链表的区别。 由于内容比较多,且涉及到代码的编写和验证,本知识点将分单链表、双链表、循环链表3次进行介绍。 本人...

阅读全文 →
OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!