彻底搞懂时间复杂度和空间复杂度

彻底搞懂时间复杂度和空间复杂度

刚开始学编程时，经常会遇到一个很困惑的问题：

程序可以运行，结果也正确，但提交后却显示：

超时

或者

内存超限

这时候很容易产生疑问：

答案明明是对的，为什么还是不通过？

原因通常不在逻辑，而在两个核心问题：

时间复杂度过高

空间复杂度过高

这两个概念看起来抽象，其实本质很简单。真正的难点不在理解，而在做题时能不能用出来。

一、为什么比赛一定要看复杂度

先看一个最基础的问题：

在一组数中找最大值：

3 7 2 9 5

最直接的方法是从头到尾扫描一遍：

int maxn = a[0];
for (int i = 1; i < n; i++) {
    if (a[i] > maxn) {
        maxn = a[i];
    }
}

当数据量很小时，这段代码几乎瞬间完成。

但当数据规模变成 100 万甚至更大时，运行时间就变得关键。

在算法比赛中，例如 GESP、CSP，常见数据范围是：

1 <= n <= 100000

这不是随便写的，而是在提示：

当前写法如果不够高效，很可能直接超时。

二、必须建立的核心意识：操作次数

程序本质上是在“重复执行操作”。

循环一次，就是一次操作。

循环一百万次，就是一百万次操作。

所以真正需要关注的是：

总共执行了多少次操作。

而不是代码写了多少行。

三、时间复杂度的本质

时间复杂度描述的是：

当数据规模变大时，程序运行时间的增长趋势。

例如：

for (int i = 0; i < n; i++) {
    cout << i;
}

执行次数是 n 次。

n=10 → 执行10次

n=1000 → 执行1000次

这种增长方式称为：

O(n)，线性增长。

四、一个重要经验：运行次数估算

竞赛中常用一个经验：

1 秒 ≈ 1 亿次简单操作

据此可以快速判断：

10⁷（千万级）：安全

10⁸（亿级）：临界

10⁹（十亿级）：基本超时

这个估算非常实用。

五、常见复杂度模型

1. 单循环

for (int i = 0; i < n; i++) {}

O(n)

2. 双重循环

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {}
}

O(n²)

3. 不完全双循环（常见误区）

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {}
}

仍然是 O(n²)，只是常数变小。

4. 对数级循环

for (int i = n; i > 0; i /= 2) {}

执行次数为：

n → n/2 → n/4 → …

属于 O(log n)

六、如何根据数据范围判断复杂度

数据规模 n 推荐复杂度

≤100 O(n²) 可接受

≤1000 O(n²) 勉强

≤100000 O(n)、O(n log n)

≥1000000 O(n)

看到数据范围，第一时间要想到复杂度是否匹配。

七、空间复杂度的本质

空间复杂度描述的是：

程序额外占用了多少内存。

例如：

int a[100];

占用 100 个整数空间。

int a[1000000];

空间扩大 10000 倍。

八、必须掌握的内存常识

一个 int 通常占 4 字节。

因此：

100000000 × 4 ≈ 400MB

代码：

int a[100000000];

在大多数比赛中会直接内存超限。

九、空间消耗的来源

不仅仅是数组，还包括：

map / set

vector 动态扩容

递归调用栈

递归过深会导致“栈溢出”。

十、典型题目完整优化过程

题目：判断数组中是否存在重复元素。

写法一：暴力

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (a[i] == a[j]) {
            cout << "YES";
        }
    }
}

O(n²)，大数据无法通过。

写法二：排序优化

sort(a, a + n);
for (int i = 1; i < n; i++) {
    if (a[i] == a[i - 1]) {
        cout << "YES";
    }
}

时间复杂度：O(n log n)

写法三：空间换时间

#include <set>
set<int> s;
for (int i = 0; i < n; i++) {
    if (s.count(a[i])) {
        cout << "YES";
        break;
    }
    s.insert(a[i]);
}

时间更优，但增加空间消耗。

十一、常见优化思路（高频考点）

暴力 → 排序

暴力 → 哈希（set / map）

减少循环层数

用空间换时间

十二、空间优化技巧

有些问题不需要存全部数据。

例如求最大值：

int maxn = -1;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (x > maxn) maxn = x;
}

空间几乎为常数级。

十三、做题固定流程（非常重要）

每道题建议按这个顺序：

看数据范围

想暴力解法

判断复杂度

是否需要优化

再写代码

这是稳定提升的关键。

十四、常见错误

不看数据范围

直接写双重循环

数组开得过大

递归深度失控

只测试样例就提交

十五、最终总结

时间复杂度：数据变大时，运行时间如何增长。

空间复杂度：程序额外占用多少内存。

比赛真正考察的是三点：

代码正确

运行高效

空间合理

最后一条非常关键的经验

每做完一道题，都要回头思考：

有没有更快的做法？

长期坚持，这一点会带来最明显的提升。