时间复杂度

这种题目是数据结构与算法考研（如408）或面试中的高频送分题，但也是高频陷阱题。

复习这类题目，不要靠“猜”或者“死记硬背”，而是要掌握一套**“数学建模”**的方法。一旦你建立了数学直觉，这类题看一眼就能选出答案。

以下是我总结的复习经验、技巧和核心知识点体系：

一、 核心复习心法：拒绝“直接相乘”，学会“级数求和”

很多同学做错这道题（选CO(nlog⁡n)O(n \log n)O(nlogn)），是因为用了错误的直觉：

“外层循环看起来是log⁡n\log nlogn次，内层循环看起来是nnn次，乘起来就是nlog⁡nn \log nnlogn。”

❌ 错误原因：当内层循环的次数j < i依赖于外层循环变量i时，绝对不能直接相乘！必须把每次循环的次数写出来，进行求和。

二、 三大经典模型（必背）

在复习时，你只需要把这三种最常见的循环模型搞定，90%的题目都能解决。

模型 1：等差数列模型（结果是O(n2)O(n^2)O(n2)）

特征：外层线性增长（i++），内层依赖外层（j < i）。

for(inti=0;i<n;i++){// 0, 1, 2, ..., nfor(intj=0;j<i;j++){// 内层执行 i 次// ...}}

• 数学分析：
  第1次执行0次，第2次执行1次……第n次执行n−1n-1n−1次。
  总次数S=0+1+2+⋯+(n−1)S = 0 + 1 + 2 + \dots + (n-1)S=0+1+2+⋯+(n−1)。
  这是等差数列求和，公式是n(n−1)2\frac{n(n-1)}{2}2n(n−1)​，最高次项是n2n^2n2。
• 结论：O(n2)O(n^2)O(n2)

模型 2：等比数列模型（你的这道错题，结果是O(n)O(n)O(n)）

特征：外层指数增长（i *= 2），内层依赖外层（j < i）。

for(inti=1;i<n;i*=2){// 1, 2, 4, 8, ...for(intj=0;j<i;j++){// 内层执行 i 次// ...}}

• 数学分析：
  iii的取值序列是1,2,4,8,…,2k1, 2, 4, 8, \dots, 2^k1,2,4,8,…,2k(其中2k<n2^k < n2k<n)。
  总次数S=1+2+4+8+⋯+2kS = 1 + 2 + 4 + 8 + \dots + 2^kS=1+2+4+8+⋯+2k。
  这是等比数列求和（公比为2）。
  记忆技巧：在二进制世界里，等比数列的和≈\approx≈最后一项乘以2。
  所以S≈2⋅2kS \approx 2 \cdot 2^kS≈2⋅2k。因为2k2^k2k接近nnn，所以总和接近2n2n2n。
• 结论：O(n)O(n)O(n)

模型 3：独立对数模型（结果是O(nlog⁡n)O(n \log n)O(nlogn)）

特征：外层线性增长（i++），内层不依赖具体数值，而是固定倍增（j *= 2）。

for(inti=0;i<n;i++){// 执行 n 次for(intj=1;j<n;j*=2){// 每次都执行 log n 次// ...}}

• 数学分析：
  外层固定跑nnn次。
  内层每次都跑log⁡2n\log_2 nlog2​n次（和iii无关）。
  这是真正的“直接相乘”场景。
  总次数S=n×log⁡2nS = n \times \log_2 nS=n×log2​n。
• 结论：O(nlog⁡n)O(n \log n)O(nlogn)

三、 解题通用步骤（复习操作指南）

考试遇到任何看不准的题，按这三步走：

第一步：列出iii的变化序列
不要只看for，要在草稿纸上写出iii具体变成了多少。

• 例题中：i=1,2,4,8,16,…i = 1, 2, 4, 8, 16, \dotsi=1,2,4,8,16,…

第二步：写出每一步内层语句执行的次数

• 例题中：当i=1i=1i=1执行1次，当i=2i=2i=2执行2次，当i=4i=4i=4执行4次……

第三步：列式求和并判断量级（最关键）

• 式子：1+2+4+⋯+最后一项1 + 2 + 4 + \dots + \text{最后一项}1+2+4+⋯+最后一项。
• 判断技巧：
  • 如果是1+2+3…(均匀增加)，总量级是最后一项的平方 ->O(n2)O(n^2)O(n2)。
  • 如果是1+2+4…(越加越大，成倍增加)，总量级由最后一项决定（前面的加起来都没最后一项大），直接看最后一项是谁 ->O(n)O(n)O(n)。
  • 如果是n + n/2 + n/4…(越加越小)，总量级由第一项决定 ->O(n)O(n)O(n)。

四、 避坑经验总结

1. 看到i *= 2别急着选log⁡n\log nlogn：

   • 如果它单独出现，是log⁡n\log nlogn。
   • 如果它作为外层循环，且内层循环是j < i（累加型），答案通常是O(n)O(n)O(n)。
   • 如果它作为外层循环，且内层循环是j < n（固定型），答案是O(nlog⁡n)O(n \log n)O(nlogn)。

2. 对数级的本质：
   只有当问题规模每次缩减一半（如二分查找）或者循环变量每次乘以2且独立执行时，才会出现log⁡n\log nlogn。

3. 常数项忽略：
   如果是i *= 3或者i += 2，分析方法一样。

   • i *= 3依然是等比数列，O(n)O(n)O(n)。
   • i += 2依然是等差数列，仅系数变化，O(n2)O(n^2)O(n2)。

五、 应该掌握的数学公式

复习时，把这三个公式背下来，考试就能横着走：

1. 等差数列求和：
   1+2+⋯+n=n(n+1)2⇒O(n2)1 + 2 + \dots + n = \frac{n(n+1)}{2} \Rightarrow O(n^2)1+2+⋯+n=2n(n+1)​⇒O(n2)
2. 等比数列求和 (q>1q > 1q>1)：
   1+2+4+⋯+2k=2k+1−1⇒O(2k)=O(n)1 + 2 + 4 + \dots + 2^k = 2^{k+1} - 1 \Rightarrow O(2^k) = O(n)1+2+4+⋯+2k=2k+1−1⇒O(2k)=O(n)
3. 调和级数求和（较难题目会考）：
   1+12+13+⋯+1n≈ln⁡n⇒O(log⁡n)1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \approx \ln n \Rightarrow O(\log n)1+21​+31​+⋯+n1​≈lnn⇒O(logn)
   (考点：比如for(i=1;i<n;i++)里面套一个for(j=1; j<n; j+=i))

复习建议：
把你做过的所有时间复杂度题目拿出来，按上面的三大模型进行分类。你会发现90%的题目都逃不出这个圈子。这样复习完，你心里就非常有数了。