【信奥业余科普】C++ 的奇妙之旅 | 29：别让 TLE 和 MLE 偷走你的分——复杂度估算与数据范围速查

发表于 2026/06/13

作者 OneCoder

次浏览 18 分钟阅读

在前面的文章中，我们学习了文件重定向操作 freopen。有了它，我们的代码就可以规范地在评测机上进行输入和输出。

但在实际的信奥比赛（如 GESP、CSP-J/S）中，光是写出“能运行出正确答案”的代码是不够的。每道题目都对资源有着极其严格的限制，通常表现为：

时间限制：例如 1.0s（1.0 秒）
空间限制：例如 256MB（256 兆字节）

如果你的程序运行时间超过了限制，就会遭遇 TLE（Time Limit Exceeded，运行超时）；如果占用的内存超过了限制，就会遭遇 MLE（Memory Limit Exceeded，内存超限）。两者都会导致你失去该测试点的分数。

那么，我们该如何预估自己的代码会不会超时或超内存呢？这就需要用到时间复杂度与空间复杂度。本文不谈复杂的数学公式和推导，我们直接用具体的代码实例和直观的数据大小，带大家快速建立对复杂度的感觉。

往期回顾：

一、时间复杂度：1 秒钟，程序能跑多少次？

在计算机科学中，时间复杂度用大写字母 $O$（Big O）来表示。我们不需要去抠它的数学定义，只需要记住一个在信奥竞赛中通用的“黄金法则”：

[!IMPORTANT] 竞赛黄金法则：在主流的信奥评测机上，C++ 程序在 1 秒钟内 大约可以执行 $10^8$（1 亿）次 基础运算（如加减乘除、大小比较、数组读写等）。

利用这个法则，我们来看看常见的时间复杂度，它们在代码中长什么样，以及在 1 秒的限制下，它们能处理多大的数据量（通常用 $N$ 表示）。

1.1 常见时间复杂度实例与数据范围

[!NOTE] 什么是“数据范围 $N$”？ 在算法比赛中，每道题都会在“数据范围”一栏明确写出 $N$ 的最大值（例如 $N \le 10^5$ 或 $N \le 10^{18}$），代表测试数据的最大规模。下文中的 【数据范围 $N$】 是指：在 1 秒的时间限制下，如果题目给出的 $N$ 在这个级别内，我们使用该时间复杂度的算法是安全的（不会超时）。 例如，如果题目给出的 $N$ 达到了 $10^{18}$ 级别，你就绝对不能使用 $O(N)$ 算法（需要跑几百年），而必须使用 $O(\log N)$ 或 $O(1)$ 级别的算法。

① $O(1)$ —— 常数复杂度 (Constant Time)

【代码长相】：没有任何循环，只有简单的算术运算或单次数组/容器访问。

  
int a = 10, b = 20;
int sum = a + b;           // 算术运算，O(1)
int val = my_vector[5];    // 数组/vector通过下标直接访问，O(1)

【计算速度】：瞬间完成，忽略不计。 【数据范围 $N$】：$N$ 可以是任意大小（哪怕是 $10^{18}$ 甚至更大，只要不超过数据类型本身的上限即可）。

② $O(\log N)$ —— 对数复杂度 (Logarithmic Time)

【代码长相】：每次折半的数据查找，或者循环中变量每次乘/除以 2。

  
// 实例 1：二分查找
std::lower_bound(a, a + n, target);

// 实例 2：折半循环
for (int i = 1; i <= n; i *= 2) {
    // 每次 i 翻倍，循环一共执行约 log2(N) 次
}

【计算速度】：极快。因为是折半递减/递增，即使 $N = 10^{18}$（一百万万亿，即 long long 类型的上限附近），$\log_2(10^{18}) \approx 60$ 次运算，在计算机中仅需微秒级（百万分之一秒）即可完成。 【数据范围 $N$】：$N$ 最大可达 $10^{18}$ 级别（因此，如果题目中 $N$ 极大，二分查找等对数级算法往往是唯一的解法）。

③ $O(N)$ —— 线性复杂度 (Linear Time)

【代码长相】：单层 for 循环，将数据从头到尾扫一遍。

  
int sum = 0;
for (int i = 0; i < n; ++i) {
    sum += a[i]; // 循环执行 N 次
}

【计算速度】：当 $N = 10^8$ 时，刚好达到 1 秒钟的红线。 【数据范围 $N$】：$N$ 最大可达 $10^7 \sim 10^8$ 级别。如果题目中的 $N \le 10^7$，手写一个单层循环的算法绝对安全。

④ $O(N \log N)$ —— 线性对数复杂度 (Linearithmic Time)

【代码长相】：最经典的就是 C++ 标准库中的排序算法，或者利用了“二分查找”的循环。

  
// 实例 1：对长度为 N 的容器进行排序
std::sort(v.begin(), v.end());

// 实例 2：单层循环内嵌套二分查找
for (int i = 0; i < n; ++i) {
    // 循环执行 N 次，内部进行一次 O(log N) 的查找
    std::lower_bound(v.begin(), v.end(), target[i]);
}

【计算速度】：当 $N = 10^6$ 时，大约需要执行 $2 \times 10^7$ 次计算，运行时间通常在 0.1~0.2 秒左右。 【数据范围 $N$】：$N$ 最大可达 $10^5 \sim 10^6$ 级别。在大部分题目中，如果 $N = 10^5$，我们就要立刻联想到需要使用排序或者分治算法。

⑤ $O(N^2)$ —— 平方复杂度 (Quadratic Time)

【代码长相】：双重嵌套的 for 循环（如冒泡排序、两两配对检查等）。

  
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        // 内外层循环嵌套，共执行 N * N 次
        if (a[i] == a[j]) { ... }
    }
}

【计算速度】：当 $N = 10^4$（1万）时，$N^2 = 10^8$，运行时间恰好接近 1 秒。 【数据范围 $N$】：$N$ 最大可达 $1000 \sim 3000$ 级别（通常在 $N \le 2000$ 时比较安全，若 $N \ge 5000$ 则极易超时）。

⑥ $O(N^3)$ —— 立方复杂度 (Cubic Time)

【代码长相】：三重嵌套的 for 循环（如最朴素的矩阵乘法、三点组合检查等）。

  
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        for (int k = 0; k < n; ++k) {
            // 三重循环嵌套，共执行 N * N * N 次
        }
    }
}

【计算速度】：当 $N = 500$ 时，$N^3 = 1.25 \times 10^8$，已经超出了 1 秒的执行能力。 【数据范围 $N$】：$N$ 最大可达 $100 \sim 300$ 级别。

⑦ $O(2^N)$ —— 指数复杂度 (Exponential Time)

【代码长相】：通常出现在没有记忆化的递归（如直接求斐波那契数）、枚举所有子集（爆搜）等场景。

  
// 斐波那契递归，每次分裂出两个子调用
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

【计算速度】：随 $N$ 的增长极速爆炸。例如 $2^{20} \approx 10^6$（百万级），$2^{30} \approx 10^9$（10 亿级，远超 1 秒承受力）。 【数据范围 $N$】：$N$ 最大可达 $20 \sim 25$ 级别。

⑧ $O(N!)$ —— 阶乘复杂度 (Factorial Time)

【代码长相】：通常出现在全排列的枚举、旅行商问题的暴力搜索中。

  
// 生成包含 N 个元素的所有排列
do {
    // 共执行 N! 次
} while (std::next_permutation(a, a + n));

【计算速度】：增长速度比指数还恐怖。例如 $10! \approx 3.6 \times 10^6$，$11! \approx 4 \times 10^7$，$12! \approx 4.7 \times 10^8$。 【数据范围 $N$】：$N$ 最大可达 $10 \sim 11$ 级别。

1.2 总结表：如何根据题目数据范围倒推算法？

在赛场上，我们拿到题目后，首先要去看 “数据范围” 这一栏。根据 $N$ 的大小，我们可以直接从下表中找出我们能写的“最大复杂度上限”，从而锁定解题思路：

题目给定的 $N$ 范围	1秒限制下的最大时间复杂度上限	推荐/可能的算法方向
$N \le 10$	$O(N!)$	深度优先搜索（DFS）暴搜全排列
$N \le 20$	$O(2^N)$	状压 DP、DFS 枚举所有子集
$N \le 100$	$O(N^4)$ 或 $O(N^3)$	弗洛伊德算法（Floyd）、区间 DP
$N \le 1000$	$O(N^2)$	朴素动态规划、双重循环暴力、大部分图论算法
$N \le 10^5$	$O(N \log N)$	排序（`sort`）、二分查找、快速幂、线段树/树状数组
$N \le 10^7$	$O(N)$	单层循环扫描、前缀和、双指针、单调栈/单调队列
$N \le 10^9$	$O(\log N)$ 或 $O(1)$	二分答案、数论算法（如 GCD）、公式直接推导

[!TIP] 很多选手做题超时，就是因为题目给的 $N = 10^5$，但他们却写了一个双重嵌套的 $O(N^2)$ 循环。根据上表可以看出，$10^5$ 的范围只允许写 $O(N \log N)$ 或 $O(N)$ 的代码，写 $O(N^2)$ 必定超时！

二、空间复杂度：内存限制如何折算成数组大小？

空间复杂度用来衡量你的程序占用了多少内存。在实际做题时，我们极少因为定义了几个变量而内存超限。导致 MLE 的罪魁祸首几乎只有一个：数组开得太大了。

因此，我们不需要死记空间复杂度的概念，只需学会如何把字节（Byte）转换为数组长度。

2.1 基础转换公式

首先，我们需要知道 C++ 中常见数据类型占用的内存大小：

char / bool：1 字节（Byte）
int / float：4 字节（Bytes）
long long / double：8 字节（Bytes）

内存单位的换算关系如下： $1\text{ MB} = 1024\text{ KB} = 1024 \times 1024\text{ Bytes} \approx 10^6\text{ 字节}$

也就是说，1 MB 的空间，大约可以存储 $10^6$ 字节的数据。

2.2 常见数据类型数组的内存上限

我们以常见的 256MB 内存限制为例，来算算不同类型的数组最大能开到多少：

① `int` 数组的最大安全大小

一个 int 占 4 字节，那么 256MB 内存最多可以开： $\frac{256 \times 10^6\text{ 字节}}{4\text{ 字节/int}} \approx 6.4 \times 10^7\text{ 个元素}$

【实战建议】：

如果开一维 int 数组，最大长度写成 int a[50000000]（5千万）是安全的。
如果开二维 int 数组，最大大小约为 int a[7000][7000]（因为 $7000 \times 7000 = 4.9 \times 10^7$）。

② `long long` 数组的最大安全大小

一个 long long 占 8 字节，是 int 的两倍。那么 256MB 最多可以开： $\frac{256 \times 10^6\text{ 字节}}{8\text{ 字节/long long}} \approx 3.2 \times 10^7\text{ 个元素}$

【实战建议】：

一维 long long 数组，最大开到 long long a[25000000]（2千5百万）。
二维 long long 数组，最大开到 long long a[5000][5000]。

2.3 空间复杂度在代码中的直观体现

$O(1)$ 空间复杂度：只定义了几个变量，几乎不占用内存。
$O(N)$ 空间复杂度：定义了一个长度为 $N$ 的一维数组（如记录状态、存储数据）。
$O(N^2)$ 空间复杂度：定义了一个 $N \times N$ 的二维数组（如邻接矩阵、二维网格图）。

[!CAUTION] 切记：信奥比赛中，全局数组的内存是在程序启动时就一次性分配好的。千万不要在看到 $N = 10^5$ 时，随手定义一个 int grid[100000][100000]。这样的二维数组会占用大约 $40\text{ GB}$ 内存，测评系统会立刻判定你的程序为内存超限（MLE）或直接编译失败！

结语

通过上面的实例和数据对比，相信大家已经对时间和空间复杂度有了清晰而具体的感觉：

时间上：看清 $N$ 的大小，对照“1秒跑1亿次”的黄金法则，合理设计循环的嵌套层数。
空间上：记住“1MB 存 25 万个 int”，谨慎计算大数组的占用内存，避免内存超限。

掌握了复杂度的估算，你就拥有了一把在写代码前就能预测程序能否拿满分的“神兵利器”。

本篇是 【C++的奇妙之旅】 系列的完结篇。

在这 29 篇文章中，我们一起从计算机硬件演化与图灵、冯·诺伊曼体系出发，走过了 C++ 的 Hello World、变量、分支、循环、数组、指针与引用，掌握了 STL 常用容器与 <algorithm> 库，并最终学习了规范比赛的文件操作与效率分析。

掌握了这些，代表你已经完成了 C++ 编程语言基础的积淀，拿到了通往算法世界大门的钥匙！

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
"luogu-"系列题目可在洛谷题库进行在线评测。
"bcqm-"系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号

信奥业余科普, C++的奇妙之旅

科普计算机科学基础 GESP CSP C++ 复杂度时间复杂度空间复杂度

本文由作者按照 CC BY-NC-SA 4.0 进行授权

一、 时间复杂度：1 秒钟，程序能跑多少次？