---
title: "03-时空复杂度"
created: 2025-11-28
tags:
  - 算法
---

# 时空复杂度

> 📚 看题先看数据范围——范围就是提示，据此推出可用算法，再看题干基本就能锁定做法。这里先建复杂度直觉，完整板子表见 [[01-根据时间复杂度选择算法]]。

## 时间复杂度分析

一般 ACM 或者笔试题的时间限制是 1 秒或 2 秒。在这种情况下，C++ 代码中的操作次数控制在 $10^7$ 为最佳。

### 数据范围 → 算法选择

| 数据范围 | 复杂度 | 可用算法 |
| --- | --- | --- |
| $n \le 30$ | 指数级别 | dfs + 剪枝、数字排列、n 皇后、八数码；状态压缩 dp、蒙德里安的梦想、最短 Hamilton 路径 |
| $n \le 100$ | $O(n^3)$ | floyd、dp |
| $n \le 1000$ | $O(n^2)$、$O(n^2 \log n)$ | dp、二分、朴素版 dijkstra、朴素版 prim、Bellman-Ford |
| $n \le 10000$ | $O(n\sqrt{n})$ | 块状链表、分块、莫队 |
| $n \le 100000$ | $O(n \log n)$ | sort、线段树、树状数组、set/map、heap、dijkstra+heap、prim+heap、spfa、凸包、半平面交、二分 |
| $n \le 10^6$ | $O(n)$、常数较小的 $O(n \log n)$ | hash、双指针、并查集、kmp、AC 自动机 |
| $n \le 10^7$ | $O(n)$ | 双指针、kmp、AC 自动机、线性筛素数 |
| $n \le 10^9$ | $O(\sqrt{n})$ | 判断质数 |
| $n \le 10^{18}$ | $O(\log n)$ | 最大公约数、快速幂 |
| $n \le 10^{1000}$ | $O((\log n)^2)$ | 高精度加减乘除 |
| $n \le 10^{100000}$ | $O(\log n \cdot \log \log n)$ | 高精度加减、FFT/NTT |

> 常数较小的 $O(n \log n)$：sort、树状数组、heap、dijkstra、spfa。

## 具体算法分析

一般来说，k 重循环，算法时间复杂度就是 $n^k$：

![[image-daf78a4e.png]]

![[image-567a640b.png]]

![[image-5afaa2bb.png]]

spfa 算法、匈牙利算法、最大流算法时间复杂度理论值很大，但是实际运行速度很快：

![[image-90d0e5ba.png]]

动态规划问题的计算量 = 状态数量 × 状态转移的计算量：

![[image-5faa9dc9.png]]

## 空间复杂度

题目一般给 64M：

- 1 Byte = 8 bit；1 KB = 1024 Byte；1 MB = 1024×1024 Byte；1 GB = 1024×1024×1024 Byte
- bool：1 Byte；char：1 Byte
- int：4 Byte，$2^{31} \approx 2 \times 10^9$（2147483648，**10 位 10 进制**）
- double / long long：8 Byte，$2^{63} \approx 9 \times 10^{18}$（9223372036854775807，**19 位 10 进制**）
- long double：16 Byte
- \_\_int128：$10^{38}$（85070591730234615865843651857942052864，**38 位 10 进制**）

递归也是需要空间的——递归调用了系统栈。快速排序使用了递归，所以空间复杂度是 $O(\log n)$。

---
⬅️ [[02-蓝桥杯考纲与路线]] 🏠 [[00-算法]] ➡️ [[04-刷题小贴士]]