目标:不背具体题目,而是掌握”分类判断 + 对应工具”的方法,遇到任何新题型都能拆解。
一、总口诀
“先看步进定单层,再看嵌套判独立;不独立就求和式,独立相乘最省力。”
拆解一下这四句话对应的动作:
- 先看步进定单层:这一层循环变量是怎么变化的(加减 or 乘除),决定这一层单独跑多少次。
- 再看嵌套判独立:如果有多层循环,看内层的边界条件里有没有外层变量。
- 不独立就求和式:内层边界含外层变量 → 不能直接相乘,要把内层次数写成外层变量的函数,再求和。
- 独立相乘最省力:内层边界与外层变量无关 → 各层次数直接相乘。
后面所有类型,都是这四句口诀的展开。
二、判断流程图(做题时照此走)
第1步:这一层变量怎么变?
├─ i = i+1 / i = i+c → 等差型,单层 O(n)
└─ i = i*2 / i = i/2 → 等比型,单层 O(log n)
第2步:有没有嵌套?
├─ 没有 → 到此结束,直接得出该层复杂度
└─ 有 → 进入第3步
第3步:内层边界里有没有外层变量(比如 j<i, j<n-i)?
├─ 没有(边界是常数或n)→ 各层次数直接相乘
└─ 有 → 把内层次数写成 f(外层变量),对外层变量求和
(这一步要判断 f 是线性/平方/常数/对数中的哪一种)
第4步:循环体内的单次操作是不是 O(1)?
├─ 是 → 不用额外处理
└─ 不是(比如调用了另一个函数、字符串比较)→ 循环次数 × 单次操作耗时
第5步:循环条件是不是复合表达式(比如 i*i<n)?
├─ 不是 → 跳过
└─ 是 → 先反解出变量的真实范围(比如 i*i<n 反解成 i<√n),
再把这个范围代入第1~4步
类型①:等差型(单层循环,基础款)
特征:i = i + 1 或 i = i + c,即每次加一个固定值。
结论:循环次数 = (终止值 − 起始值) / 步长 = O(n)
例题
int sum = 0;
for (int i = 0; i < n; i++) {
sum += i;
}- i 从 0 到 n-1,每次 +1,一共跑 n 次。
- 时间复杂度:O(n)
记忆口诀:加减法是”走路”,走几步就是几步,不绕弯。
类型②:等比型(单层循环,乘除变化)
特征:i = i * 2 或 i = i / 2,变量按倍数变化。
结论:问的是”2的几次方能到n”,即 2^k ≈ n → k ≈ log₂n → O(log n)
例题
int i = 1;
while (i < n) {
i = i * 2;
}- i 的取值序列:1, 2, 4, 8, 16, …, 直到 ≥ n。
- 设跑了 k 次,则 2^k ≥ n,解得 k ≥ log₂n。
- 时间复杂度:O(log n)
记忆口诀:乘除法是”跳级”,每次翻倍,跳 log n 次就到头。判断标志:看变量是 加/减 还是 乘/除,这是区分①②最快的方法。
类型③:嵌套且内层独立于外层(双层循环,边界是常数/n)
特征:内层循环的终止条件里不含外层变量。
结论:两层各自的次数直接相乘。
例题
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) { // j 的范围和 i 无关,恒为 n
count++;
}
}- 外层跑 n 次,内层每次都跑 n 次,互不影响。
- 时间复杂度:O(n) × O(n) = O(n²)
变体:如果内层是 for(j=0;j<m;j++)(m 是另一个和 i 无关的常数或变量),结果是 O(n × m),同样是相乘逻辑。
记忆口诀:内层边界”看不见”外层变量 → 两层各干各的 → 直接相乘。
类型④:嵌套且内层依赖外层(双层循环,边界含 i)—— 最容易出新题型的地方
特征:内层循环的终止条件里含外层变量,比如 j<i、j<n-i、j<2i、j<i*i。
结论:不能直接相乘!要把内层执行次数写成 f(i),然后对外层变量求和:
关键在于识别 f(i) 是下面哪一种,然后套对应的求和结果:
④-1 f(i) 是线性的(比如 j<i,内层次数=i)
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) { // 内层跑 i 次
count++;
}
}- 总次数 = 0 + 1 + 2 + … + (n-1) = n(n-1)/2 ≈ O(n²)
- 推广结论:只要内层次数与外层变量成正比(线性关系),总复杂度 = O(外层范围²)。
这正是”2025年408第1题”的本质:外层范围是 √n(因为条件是 i*i<n),内层次数与i成正比,所以总复杂度 = O((√n)²) = O(n),对应选项 B。
④-2 f(i) 是平方关系(比如 j<i*i)
for (int i = 0; i < n; i++) {
for (int j = 0; j < i*i; j++) {
count++;
}
}- 总次数 = Σ i² ≈ n³/3 → O(n³)
④-3 f(i) 是常数(比如 j<10,内层与i无关但也不是n)
for (int i = 0; i < n; i++) {
for (int j = 0; j < 10; j++) {
count++;
}
}- 内层恒定跑10次(常数),总次数 = 10 × n → O(n)
- 这种情况看起来”依赖i”其实并不依赖,属于③的特例,但很多人会被”看起来是嵌套”误导成O(n²),要小心。
④-4 f(i) 是对数关系(比如内层是 j 每次乘2,且上界是i)
for (int i = 1; i < n; i++) {
for (int j = 1; j < i; j *= 2) { // 内层是等比型,跑 log(i) 次
count++;
}
}- 总次数 = Σ log(i),i从1到n,约等于 O(n log n)
记忆口诀:“内层含外层变量,先写 f(i) 再求和;线性平方n²n³,常数对数别看花。“
类型⑤:内层边界本身也在等比变化(嵌套中的经典陷阱)
特征:外层是等比型(log n次),内层次数刚好等于外层当前变量值。
例题(极易算错)
for (int i = 1; i < n; i *= 2) { // 外层:1,2,4,8,...,n,共 log n 次
for (int j = 0; j < i; j++) { // 内层:跑 i 次
count++;
}
}直觉上的错误算法:外层 log n 次,内层最多跑 n 次,“感觉”应该是 O(n log n)。
正确算法:把每一轮外层对应的内层次数加起来,是一个等比数列求和: (等比数列求和的结果由最大的一项主导,前面所有项加起来也不超过最大项的2倍)
- 时间复杂度:O(n),不是 O(n log n)!
记忆口诀:“外层跳级、内层线性叠加”,先看总和是不是等比数列,等比数列求和看最大项,别被”次数相乘”的直觉带偏。
类型⑥:循环体内不是 O(1) 操作(隐藏耗时)
特征:循环体内部调用了函数、做了字符串比较/拷贝、甚至是递归——这些单次操作本身不是常数时间。
例题
for (int i = 0; i < n; i++) {
if (strcmp(arr[i], target) == 0) { // strcmp 本身是 O(m),m是字符串长度
found = true;
}
}- 外层跑 n 次,每次调用 strcmp 耗时 O(m)。
- 时间复杂度:O(n × m),不能简单写成 O(n)。
记忆口诀:数循环次数之前,先看循环体里”是不是只做了一次赋值/比较/自增”,只要出现函数调用、字符串操作、嵌套数据结构访问,就要把它的耗时乘进去。
类型⑦:复合条件(条件不是简单的 i<n,而是需要反解)
特征:循环条件是 i*i<n、i*i*i<n、2^i<n 这类需要先”解方程”才能看出真实范围的表达式。
例题(本质就是2025年真题第1题)
for (int i = 0; i*i < n; i++) {
for (int j = 0; j < i; j++) {
count++;
}
}处理步骤:
- 先反解外层条件:
i*i < n→i < √n,所以外层真实范围是 O(√n),不是 O(n)。 - 再看内层:
j<i,属于类型④-1(线性关系)。 - 套用④-1的结论:内层与外层变量线性相关 → 总复杂度 = O(外层范围²) = O((√n)²) = O(n)。
记忆口诀:看到循环条件里变量带指数/带乘积,先解出变量的”真实跑动范围”,再按前面①-⑥的规则套。反解是唯一要多做的一步,规则本身没变。
三、时间复杂度速查表
| 类型 | 特征 | 结论 |
|---|---|---|
| ① 等差 | i=i+1 | O(n) |
| ② 等比 | i=i*2 或 i=i/2 | O(log n) |
| ③ 嵌套独立 | 内层边界与i无关 | 两层相乘 |
| ④-1 嵌套线性 | j<i | O(外层范围²) |
| ④-2 嵌套平方 | j<i² | O(外层范围³) |
| ④-3 嵌套常数 | j<常数 | O(外层范围) |
| ④-4 嵌套对数 | 内层等比、上界为i | O(n log n) |
| ⑤ 双层等比叠加 | 外层等比,内层=当前i | O(最大项),不是相乘 |
| ⑥ 非O(1)操作 | 循环体调用函数/字符串操作 | 循环次数×单次耗时 |
| ⑦ 复合条件 | i*i<n 等 | 先反解范围,再套①-⑥ |
四、空间复杂度怎么算——同样给一套框架
空间复杂度和时间复杂度的思路不一样,不是数”跑了几次”,而是数”同时占用了多少额外存储”。
核心原则
注意:只算”额外”辅助空间,不算输入数据本身占的空间(除非题目特别说明要算输入空间)。
判断步骤
第1步:找出所有会占用内存的变量/结构,分成两类
- 固定大小的(几个 int、几个指针)→ 这些是 O(1),和 n 无关
- 大小随 n 变化的(数组、递归调用栈、动态开辟的内存)→ 这些才是需要分析的对象
第2步:分情况计算
情况A:额外开辟了与n相关的数组/表
void func(int n) {
int *arr = (int*)malloc(n * sizeof(int)); // 开了一个大小为n的数组
...
}- 这个数组大小正比于 n → 空间复杂度 O(n)
情况B:递归调用(最容易漏算的部分)
核心思路:递归的空间开销,主要来自调用栈的深度,因为每次递归调用都要在栈上保留一份局部变量、返回地址,深度多深,栈上就叠多少层。
int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}- 递归调用链条:factorial(n) → factorial(n-1) → … → factorial(1)
- 每一层调用都要占一份栈帧,栈的最大深度 = n
- 空间复杂度:O(n)(哪怕每次递归只用了几个变量,因为要叠n层,所以是O(n),而不是O(1))
递归空间复杂度记忆口诀:“递归深度就是空间”,不管每层用多少变量,看这个递归最深能叠多少层,答案就是这个深度的量级。
变体:折半递归(比如归并排序、二分查找的递归写法)
void binarySearch(int arr[], int low, int high) {
if (low > high) return;
int mid = (low + high) / 2;
...
binarySearch(arr, low, mid - 1); // 每次只递归一边,问题规模减半
}- 每次递归问题规模减半,调用深度是 log₂n 层
- 空间复杂度:O(log n)
变体:树形递归(比如归并排序真正同时展开两边)
void mergeSort(int arr[], int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid+1, r); // 两个分支都会递归下去
merge(arr, l, mid, r);
}- 虽然会分裂成两个分支,但同一时刻栈上只有一条调用链(因为程序是顺序执行,不是真的同时跑两个分支),最大栈深度仍然是 O(log n)
- 但如果 merge 操作本身需要额外数组(归并排序的合并步骤通常需要),那部分额外数组是 O(n),所以归并排序整体空间复杂度是 O(n)(数组)+ O(log n)(递归栈)= 以 O(n) 为主
记忆口诀:递归空间看”调用链最长能拉多长”,不是看”一共调用了多少次”(那是时间复杂度关心的事)。
情况C:只用了常数个变量,没有额外数组、没有递归
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
}- 只用了 sum、i 两个变量,不随 n 增长
- 空间复杂度:O(1)
空间复杂度速查表
| 情况 | 特征 | 结论 |
|---|---|---|
| 只用常数个变量 | 没有额外数组、没有递归 | O(1) |
| 开辟了大小为n的数组/表 | malloc(n) 之类 | O(n) |
| 单向递归(一路递归到底) | factorial 型 | O(递归深度) |
| 折半递归 | 二分查找型,每次问题减半 | O(log n) |
| 树形递归+需要额外合并数组 | 归并排序型 | 看数组部分,通常O(n) |
五、做题时的最终检查清单
拿到一道循环题,按顺序问自己:
- 每一层的步进方式是加减还是乘除?(判断这一层单独是O(n)还是O(log n))
- 有没有嵌套?内层边界含不含外层变量?
- 如果含,内层次数f(i)是线性/平方/常数/对数中的哪一种?
- 循环条件是不是复合表达式,需不需要先反解范围?
- 循环体内的单次操作是不是真的O(1)?
- 【空间】有没有开辟额外数组?大小是不是随n变化?
- 【空间】有没有递归?递归的最大调用深度是多少?
这七个问题问完,基本上408里能出的循环时间/空间复杂度题都能覆盖,不管换成什么新的条件表达式或循环结构,都是这几类的排列组合。