⏱️ 算法的时间和空间效率分析
程序好不好，比一比「跑多快」和「占多大」。复杂度用大 O 记法给算法「分级」：O(1) 眨眼完成、O(n) 数一下、O(n²) 两两配……这一页教你把循环、递归、排序、图遍历的时间复杂度数出来！
考纲知识点：算法时间和空间复杂度的一般分析方法
各类算法（包括排序算法、查找算法、树和图的遍历算法、搜索算法、分治及动态规划算法等）的时间和空间复杂度
各类算法（包括排序算法、查找算法、树和图的遍历算法、搜索算法、分治及动态规划算法等）的时间和空间复杂度
📖
考纲 · 知识点详述
摘自《CCF编程能力等级认证 C++&Python 认证标准》C++ 八级
- (7)算法的时间和空间效率分析。能够掌握较为复杂算法的时间和空间复杂度分析方法，能够分析各类算法（包括排序算法、查找算法、树和图的遍历算法、搜索算法、分治及动态规划算法等）的时间和空间复杂度。
📚
先学一学
花 6 分钟读完下面 5 课，再去闯关就不慌啦
1
🏷️ 大 O 记法：给算法「分级」
时间复杂度回答「数据变多 n 倍，工作量怎么变」。我们只关心「增长等级」，用大 O 表示：O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ)…常数和低阶项都忽略。
🪜 从快到慢排一排
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
n 很大时，差一级可能就是「眨眼」和「等一年」的区别。
n 很大时，差一级可能就是「眨眼」和「等一年」的区别。
💡 口诀：一、对、线、线对、平方、指数——越来越慢。
⏰ 空间复杂度
空间复杂度回答「额外用了多少内存」，记法一样。比如开一个 n 的数组 → O(n)；开 n×n 的二维数组 → O(n²)。
2
🔁 循环怎么数：看它跑几趟
1️⃣ 一重循环 → O(n)
从 1 走到 n 一次 → O(n)：
for (int i = 1; i <= n; i++) sum += i;
2️⃣ 两重循环 → O(n²)
外层 n 次 × 内层 n 次 → O(n²)：
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) cnt++;
for (int j = 1; j <= n; j++) cnt++;
3️⃣ 每轮砍一半 → O(log n)
while 里每轮把 n 除以 2（二分、倍增、求最大公约数）→ 只跑约 log₂n 次：while (n > 1) n /= 2;。
💡 口诀：循环一重 O(n)，二重 O(n²)；每轮减半出 log。
3
📚 常见算法的复杂度小抄
🧾 排序与查找
冒泡/选择排序 O(n²)；快速/归并排序平均 O(n log n)；在有序数组里二分查找 O(log n)；在 n 个元素里线性查找 O(n)。
🌳 树与图
遍历/释放一棵 n 个结点的二叉树：每个结点访问一次 → O(n)；DFS、BFS 遍历有 V 个点 E 条边的图 → O(V+E)；二叉排序树查找平均和树高有关。
🪆 递归
递归时间复杂度要看「调用几次 × 每次多少工作」。比如二分式递归每层减半 → O(log n) 或 O(n log n)；斐波那契朴素递归会指数爆炸 O(2ⁿ)（或 O(φⁿ)）。
💡 口诀：排序记 O(n log n)，图遍历 O(V+E)，递归看层数和每层工作量。
4
💻 实战：给一段代码「掐表」
📐 例：gcd 递归
看得懂就好，不用背。欧几里得算法每轮 n 变成 n % m，规模迅速变小 → 最差 O(log n)：
int gcd(int m, int n) {
if (m == 0) return n;
return gcd(n % m, m);
}
if (m == 0) return n;
return gcd(n % m, m);
}
递归一次参数就小一大截，大约对数级，不是 O(n)。
🌀 例：内外循环数格子
外层跑 n 次，内层跑到 √n → 一共约 n·√n：
for (int i = 1; i <= n; i++)
for (int j = 1; j * j <= i; j++) s += j;
for (int j = 1; j * j <= i; j++) s += j;
内层循环次数随 i 变（最多 √n），总数约 n·√n，不是 n²。
5
🌟 为什么工程师天天算复杂度
🚀 数据一大就露馅
一秒钟电脑大约能做上亿次简单操作。n = 100000 时：O(n) 很轻松，O(n²) 就 100 亿次、跑不动了。所以大数据系统（搜索引擎、数据库、导航）特别看重复杂度，差一级算法就「超时」。写程序前先估复杂度，是工程师的基本功。
💡 口诀：先估复杂度再写码，免得数据一大就卡死。
🎯
闯关小锦囊 · 考点提醒
- 复杂度排序：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)。
- 一重循环 O(n)、两重 O(n²)；每轮减半 → O(log n)；外层 n、内层 √n → O(n√n)。
- 二叉排序树查找：最好 O(1)（根就是目标），最差 O(n)（歪脖子树）；平均正比于树高。
- 释放 n 个结点的二叉树 / 遍历树 → O(n)；图 DFS、BFS → O(V+E)。
- 递归看「调用次数 × 每次工作量」：gcd 欧几里得最差 O(log n)，朴素斐波那契会到 O(2ⁿ)。
- 空间复杂度：数组多大就记多大，比如 n×n → O(n²)。
🎮
学完了？来闯关！
下面 15 个小挑战，点一点就能玩
Demo 原型 · 每个知识点独立页面 · 暂不含真实编译与进度存储。