29：别让 TLE 和 MLE 偷走你的分——复杂度估算与数据范围速查

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

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

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

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

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

往期回顾：

• 第一部分【计算机历史】系列文章合集（共8篇）
• 第二部分【C++的奇妙之旅】前28篇合集

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

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

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

1.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$ 的大小，我们可以直接从下表中找出我们能写的“最大复杂度上限”，从而锁定解题思路：

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

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

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

2.1 基础转换公式

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

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

内存单位的换算关系如下：

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

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

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

① int 数组的最大安全大小

一个 int 占 4 字节，那么 256MB 内存最多可以开：

【实战建议】：

• 如果开一维 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 最多可以开：

【实战建议】：

• 一维 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$ 的二维数组（如邻接矩阵、二维网格图）。

结语

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

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

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

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

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

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

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

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