目标:不背具体题目,而是掌握”分类判断 + 对应工具”的方法,遇到任何新题型都能拆解。


一、总口诀

“先看步进定单层,再看嵌套判独立;不独立就求和式,独立相乘最省力。”

拆解一下这四句话对应的动作:

  1. 先看步进定单层:这一层循环变量是怎么变化的(加减 or 乘除),决定这一层单独跑多少次。
  2. 再看嵌套判独立:如果有多层循环,看内层的边界条件里有没有外层变量。
  3. 不独立就求和式:内层边界含外层变量 → 不能直接相乘,要把内层次数写成外层变量的函数,再求和。
  4. 独立相乘最省力:内层边界与外层变量无关 → 各层次数直接相乘。

后面所有类型,都是这四句口诀的展开。


二、判断流程图(做题时照此走)

第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++;
    }
}

处理步骤:

  1. 先反解外层条件:i*i < n → i < √n,所以外层真实范围是 O(√n),不是 O(n)。
  2. 再看内层:j<i,属于类型④-1(线性关系)。
  3. 套用④-1的结论:内层与外层变量线性相关 → 总复杂度 = O(外层范围²) = O((√n)²) = O(n)。

记忆口诀:看到循环条件里变量带指数/带乘积,先解出变量的”真实跑动范围”,再按前面①-⑥的规则套。反解是唯一要多做的一步,规则本身没变。


三、时间复杂度速查表

类型特征结论
① 等差i=i+1O(n)
② 等比i=i*2 或 i=i/2O(log n)
③ 嵌套独立内层边界与i无关两层相乘
④-1 嵌套线性j<iO(外层范围²)
④-2 嵌套平方j<i²O(外层范围³)
④-3 嵌套常数j<常数O(外层范围)
④-4 嵌套对数内层等比、上界为iO(n log n)
⑤ 双层等比叠加外层等比,内层=当前iO(最大项),不是相乘
⑥ 非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里能出的循环时间/空间复杂度题都能覆盖,不管换成什么新的条件表达式或循环结构,都是这几类的排列组合。