考纲要求
- 理解时间复杂度描述的是运算次数随数据规模增长的趋势，而不是具体秒数。
- 能识别常见复杂度：常数 O(1)、线性 O(n)、平方 O(n²)、对数 O(log n)。
- 能根据循环层数与循环次数写出算法的时间复杂度。
- 能根据数据范围判断算法是否可行，例如 n 达到十万级时尽量用 O(n log n) 或 O(n)。
典型题型
- 给出一段程序，要求写出时间复杂度。
- 比较两个算法在 n 增大时的快慢。
- 根据数据范围选择合适的算法。
常见错误
- 只看循环层数不看循环次数，误以为所有双重循环都是 O(n²)。内层次数固定时是常数。
- 把 O(n) 理解成「一定要跑 n 次」，忽略常数因子和低阶项。
- 只看最内层语句，忽略外层循环带来的倍增。
- 用运行时间的绝对值比较算法，而不是看数据规模增大时的趋势。
深入理解
大 O 只看增长趋势
时间复杂度描述的是「数据规模 n 变大时，运算次数怎么增长」，不是精确的秒数。写成大 O 时只保留最高阶项、去掉常数系数：3n² + 5n + 100 记作 O(n²)，n/2 记作 O(n)。
原因是常数在 n 很大时影响可以忽略：n = 10000 时，3n² 中的 5n 和 100 只占千分之几。这也解释了为什么复杂度只在规模足够大时才有意义。
读代码估算的三个步骤
第一步，找循环：一层循环对应 O(n)，两层嵌套对应 O(n²)，三层对应 O(n³)。第二步，看循环范围：如果内层每次只跑固定 10 次，那还是 O(n)，不构成 n²。第三步，看循环变量怎么变：每次都减半（i /= 2）的循环是 O(log n)，因为从 n 减到 1 只需约 log₂n 步。
常见复杂度从小到大排：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ)。排序算法的分水岭就在 O(n log n) 与 O(n²) 之间。
空间复杂度同样要看趋势
空间复杂度统计的是额外申请的内存，输入数据本身不算。int a[100000]; 占 O(n)，几个临时变量是 O(1)。冒泡排序只用了两个临时变量，空间复杂度 O(1)；归并排序需要额外的辅助数组，是 O(n)。
题目说「空间限制 256 MB」时，可以粗算能开多大的数组：一个 int 占 4 字节，256 MB 约可容纳 6700 万个 int。二级学过的容量换算（1 MB = 1024 KB）在这里直接用得上。
自编例题
两个循环的复杂度
分别写出下面两段代码的时间复杂度。
for (int i = 0; i < n; i++) sum += i; // A
for (int i = 0; i < n; i++)
for (int j = 0; j < 100; j++) sum += i; // BA 的循环体执行 n 次，复杂度是 O(n)。B 是双重循环，但内层固定执行 100 次，总次数是 100n，常数因子在复杂度中忽略，所以仍然是 O(n)。只有当内层循环次数随 n 变化时才会出现 O(n²)。估算复杂度时要数清楚循环体实际执行了多少次，而不是简单看嵌套了几层；同时只保留最高阶项，例如 3n² 加 2n 记作 O(n²)。
相关真题
这块内容在整条路线里的位置：GESP C++ 4 级备考路径。
READY TO START
开始练习
先做一套本级别测评，报告会指出哪些知识点需要重点补；再回到本页对照考纲要求逐条核对，把不确定的条目记下来集中练。
常见问题
大 O 是什么意思？
大 O 描述运算次数随数据规模增长的上界趋势，忽略常数因子和低阶项，用来比较算法在规模变大时的表现。
O(n log n) 是怎么来的？
常见于每层把问题规模减半、共 log n 层，每层处理 n 个元素的算法，例如归并排序和快速排序的平均情况。
复杂度高的算法一定慢吗？
不一定。数据规模很小时低复杂度算法可能因常数开销更大而更慢，但规模增大后增长趋势决定优劣。