当前位置：首页 > news >正文

时间复杂度

news 2026/6/28 1:08:53

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

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

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

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

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

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

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

特征：外层线性增长（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)

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

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

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

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

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

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

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

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

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

式子：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)。

看到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且独立执行时，才会出现log⁡n\log nlogn。
常数项忽略：
如果是i *= 3或者i += 2，分析方法一样。
- i *= 3依然是等比数列，O(n)O(n)O(n)。
- i += 2依然是等差数列，仅系数变化，O(n2)O(n^2)O(n2)。

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

等差数列求和：
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)
等比数列求和 (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)
调和级数求和（较难题目会考）：
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))