408 循环时间复杂度通关母题与全解模型(含级数公式)

【学长导读】 时间复杂度分析是 408 数据结构每年的“开门第一题”(第1题),分值 2 分。 很多同学记了笔记还是总做错,本质原因是盲目把多层循环当成“相乘”。 只要记住一句话:“内层与外层无关直接乘;内层与外层有关写求和();翻倍/折半写项数,最后一项定乾坤!” 本卡把 408 历年真题及可能考到的所有循环类型、内层次数寻找技巧、必备级数公式、典型例题一网打尽,彻底解决这个痛点!


模块一:考研必背求和与级数公式速查表

考场上不用推导,这几个高中数学公式必须刻在 DNA 里:

0. 救命必学:循环中的“通项”与“总项数”到底怎么求?(拒绝蒙圈)

很多同学看到 和项数 就头大,其实循环里的数列求通项极其死板,只有 “加法累加(等差)” 和 “乘法翻倍(等比)” 两大套路:

规则 A:每次做加法(等差型,如 i++ 或 i += d)

  • 原理:第 1 步是初始值,每过一轮加一次公差 。
  • 第 轮后的变量值(通项):
    • 例子:for (int i = 1; i <= n; i += 2)
      • 第 1 轮:
      • 第 2 轮:
      • 第 3 轮:
      • 第 轮通项:
  • 怎么求总轮数(总项数 )?
    • 令最后一轮通项等于终止边界: 项!

规则 B:每次做乘法(等比型,如 i *= 2 或 i *= 3)

  • 原理:第 1 步是初始值,每过一轮乘一次公比 。
  • 第 轮后的变量值(通项):
    • 例子:for (int i = 1; i < n; i *= 2)
      • 第 1 轮:
      • 第 2 轮:
      • 第 3 轮:
      • 第 轮通项:
  • 怎么求总轮数(总项数 )?
    • 设一共跑了 轮,最后一轮变量值为 。
    • 根据循环条件 :

规则 C:内层执行次数与外层变量的关系转化(最核心!)

  • 题干代码是 for (int j = 0; j < i; j++):
    • 这意味着:在第 轮中,内层的循环次数直接等于这一轮外层变量 的值!
    • 所以内层在第 轮的执行次数通项 。
    • 于是总执行次数就是把这 轮的通项加起来:

1. 等差数列求和公式

  • 通项:(首项 ,公差 ,第 项)
  • 求和:
  • 应试最高频特例:

2. 等比数列求和公式(最容易被阴的考点)

  • 通项:(首项 ,公比 ,第 项)
  • 求和公式():
  • 应试最高频特例(公比 ):
  • 🔥【秒杀黄金口诀】:

    公比 的等比数列求和,其总体数量级由“最大那一项(最后一项)”决定!
    最后一项是 ,总和就是 。若最后一项 ,总和直接就是 !


3. 平方和与立方和公式

  • 平方和:
  • 立方和:

4. 调和级数与对数积分

  • 调和级数:
  • 对数求和(常见于 Stirling 公式衍生):

模块二:通用的破题三步法(教你怎么想)

不要试图一步看穿多层循环,严格按以下三步走:

[步骤1:分析外层变量] 
  观察外层循环控制变量 i 的变化步长:
  - 加减固定常数(i++ / i += c)   ==> 线性增长,外层共跑 n 步
  - 乘除固定常数(i *= 2 / i /= 2) ==> 指数/对数增长,外层共跑 log_2(n) 步
  - 变量自乘(i = i * i)           ==> 双重对数增长,跑 log_log(n) 步

[步骤2:看内层是否与外层相关]
  - 若【无关】:内层执行次数与 i 没有任何关系(如 j < n),直接:总次数 = 外层次数 × 内层次数。
  - 若【强相关】:内层上界或下界含有 i(如 j < i 或 j 从 i 开始),写出求和式 ∑。

[步骤3:展开求和式(前3项 + 最后一项)]
  永远在草稿纸上写出前 3 项和最后一项!套用等差、等比或积分公式秒出结果。

模块三:408 循环复杂度全场景题型与典型例题


题型一:内层与外层无关型(直接相乘)

【模型特征】

外层循环多少次,内层就老老实实跑多少次,互不干涉。

【例题 1-1】(单对数乘单对数)

for (int i = 1; i < n; i *= 2)
    for (int j = 1; j < n; j *= 2)
        count++;
  • 解析:
    • 外层 取 ,执行次数为 次;
    • 内层 取 ,执行次数同样为 次;
    • 内外无关,直接相乘:

题型二:内层与外层线性相关(等差数列模型)

【模型特征】

内层循环次数直接依赖于外层的线性步数 ,呈现 或逆向减小。

【例题 2-1】(经典双重线性循环)

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++)
        count++;
  • 草稿本推演:
    • 时,内层执行 次;
    • 时,内层执行 次;
    • ……
    • 时,内层执行 次;
  • 展开求和:

【例题 2-2】(外层步长为常数跳跃)

for (int i = 1; i <= n; i += 2)
    for (int j = i; j <= n; j++)
        count++;
  • 草稿本推演:
    • 时,内层从 到 ,跑 次;
    • 时,内层跑 次;
    • 时,内层跑 次;
    • 最后一项约为 次;
  • 展开求和:项数为 项的等差数列,首项 ,尾项 :

题型三:外层翻倍、内层依赖外层(等比数列模型 —— 2022年真题原案)

【模型特征】

外层 指数翻倍(),但内层上限是当前 (j < i)。这是考生最容易误选为 的重灾区!

【例题 3-1】(2022年 408 第1题原题)

int sum = 0;
for (int i = 1; i < n; i *= 2)
    for (int j = 0; j < i; j++)
        sum++;
  • 草稿本推演:
    • 外层 的取值依次为:(其中最后一轮 );
    • 对应内层 j < i 执行的次数依次为:
      • 次
      • 次
      • 次
      • 次
      • ……
      • 次
  • 展开求和: 利用等比数列求和:
  • 代入终止条件: 因为 ,所以 :
  • 【绝对误区提示】:不要看外层循环了 次就直接乘内层!内层不是每次跑 次,内层累加起来是一个等比级数,和就是 !

题型四:外层线性、内层折半/翻倍(对数求和 / 阶乘对数)

【模型特征】

外层步步推进(),内层每次翻倍(j *= 2)或内层与 强相关。

【例题 4-1】

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j *= 2)
        count++;
  • 草稿本推演:
    • 时,内层 跑 次;
    • 时,内层跑 次;
    • 时,内层跑 次;
    • ……
    • 时,内层跑 次;
  • 展开求和:
  • 根据斯特林公式(Stirling’s approximation):

题型五:调和级数型(跳跃步长依赖外层)

【模型特征】

外层走 ,内层每次增加 (j += i)。

【例题 5-1】(素数筛法核心结构)

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j += i)
        count++;
  • 草稿本推演:
    • 时,内层步长为 1,执行 次;
    • 时,内层步长为 2,执行 次;
    • 时,内层步长为 3,执行 次;
    • ……
    • 时,内层步长为 ,执行 次;
  • 提取公因式 展开求和:
  • 代入调和级数公式:

题型六:平方根与非标准单循环型

【模型特征】

循环变量做乘法运算(如 或 )。

【例题 6-1】(2014年 408 第1题变式)

int y = 0;
while ((y + 1) * (y + 1) <= n)
    y = y + 1;
  • 解析:
    • 循环终止条件是 ;
    • 故 ,循环一共跑了 步;
    • 复杂度:。

【例题 6-2】(双重对数型)

int i = 2;
while (i < n)
    i = i * i;
  • 推演:
    • 第 0 步:;
    • 第 1 步:;
    • 第 2 步:;
    • 第 步:;
    • 令 ;
    • 复杂度:。

模块四:考场终极秒杀自查口诀

循环结构要看准,外层内层莫乱混:
无依无靠直接乘,对数乘方看得清;
内层若被外层限,草稿纸上写前三;
1 加到 n 算等差,n 方一半跑不脱;
内翻外翻看等比,末项决定全局和;
外步为 i 调和级,提到括号 n log n;
条件带方开平方,自乘两下 log log n!

模块五:单层循环防错“死方法”(考场大脑空白必胜两招)

高频丢分重灾区

遇到 while (n >= (x + 1) * (x + 1)) x = x + 1; 这类单层循环题,最容易看走眼:

  • 看到 (x + 1) * (x + 1) 就顺手选 ;
  • 看到 x = x + 1 就顺手选 。 记住:条件里 膨胀得越快(如平方),撞到边界 就越快,循环跑的次数 反而越少(开方)!

死方法一:无脑三步套公式法(通杀一切单层循环)

不管代码长啥样,死记设循环执行了 次,然后解出 关于 的表达式:

  1. 用 表示循环变量:
    • 初始 x = 0;,每次 x = x + 1;,执行 次后,。
    • (若每次 x = x * 2,执行 次后 ;若每次 i = i * i,执行 次后 )
  2. 把“停止条件”直接改成等号 =:
    • 算渐近复杂度时常数项(如 + 1)直接扔掉,把 代入 n >= (x + 1) * (x + 1),不等号改等号:
  3. 解出 (⚠️ 题目问的是执行次数 ,千万别解反了):
    • 时间复杂度直接选 ====。

死方法二:考场兜底“代数字大法”

实在没底或脑子卡壳时,直接取个好算的数(如 ====),手动数它跑几趟:

  • x = 0: 跑第 1 次,x 变 1
  • x = 1: 跑第 2 次,x 变 2
  • ……
  • x = 9: 跑第 10 次,x 变 10
  • x = 10: 循环结束!

一共跑了 10 次。把 代进四个选项比大小:

  • (太小,排除)
  • ====(严丝合缝,直接锁定!)
  • (太大,排除)
  • (离谱,排除)