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就顺手选 。 记住:条件里 膨胀得越快(如平方),撞到边界 就越快,循环跑的次数 反而越少(开方)!
死方法一:无脑三步套公式法(通杀一切单层循环)
不管代码长啥样,死记设循环执行了 次,然后解出 关于 的表达式:
- 用 表示循环变量:
- 初始
x = 0;,每次x = x + 1;,执行 次后,。 - (若每次
x = x * 2,执行 次后 ;若每次i = i * i,执行 次后 )
- 初始
- 把“停止条件”直接改成等号
=:- 算渐近复杂度时常数项(如
+ 1)直接扔掉,把 代入n >= (x + 1) * (x + 1),不等号改等号:
- 算渐近复杂度时常数项(如
- 解出 (⚠️ 题目问的是执行次数 ,千万别解反了):
- 时间复杂度直接选 ====。
死方法二:考场兜底“代数字大法”
实在没底或脑子卡壳时,直接取个好算的数(如 ====),手动数它跑几趟:
x = 0: 跑第 1 次,x变 1x = 1: 跑第 2 次,x变 2- ……
x = 9: 跑第 10 次,x变 10x = 10: 循环结束!
一共跑了 10 次。把 代进四个选项比大小:
- (太小,排除)
- ====(严丝合缝,直接锁定!)
- (太大,排除)
- (离谱,排除)