《时间复杂度 & 空间复杂度》
一句话理解
> 时间复杂度：你的代码跑得快不快？
> 空间复杂度：你的代码占内存多不多？
就像玩游戏：
* 时间复杂度 = 通关需要多长时间
* 空间复杂度 = 游戏占了多少存储空间
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一、时间复杂度
常见复杂度（从快到慢）
复杂度 名称 通俗理解 例子 O(1) 常数时间 无论数据多少，都是一瞬间 数组按下标取值 O(log n) 对数时间 数据翻倍，只多一步 二分查找 O(n) 线性时间 数据多少，就做多少次 遍历数组 O(n log n) 线性对数 比线性慢一点 快速排序、归并排序 O(n²) 平方时间 数据翻倍，时间变4倍 冒泡排序、双重循环 O(2ⁿ) 指数时间 数据多一点，直接爆炸 递归算斐波那契
速度对比（数据量 N=1000 时）
怎么算时间复杂度？
口诀：看循环，数嵌套
复杂度的"省略规则"
* 忽略常数：O(2n) → O(n)，O(100) → O(1)
* 只保留最高次项：O(n² + n) → O(n²)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
在信奥（信息学竞赛）中，时间限制为 1 秒时，通常对应 约 ( 3 \times 10^7 ) 到 ( 10^8 ) 次简单操作（如整数加减、比较、位运算等）。
更精确的经验参考（针对 C++，O2 优化）：
* 稳定安全：( 2 \times 10^7 ) 次运算（大部分 OJ 都能过）
* 常见极限：( 5 \times 10^7 ) 次运算（较优实现，简单操作）
* 风险边界：( 1 \times 10^8 ) 次运算（可能压线过，也可能 TLE）
* 通常超时：( \ge 2 \times 10^8 ) 次运算
不同操作耗时不同：
* 整数加减、位运算：最快
* 乘法稍慢（但仍很快）
* 除法、取模：慢（约为加减法的 3~10 倍）
* 内存访问（尤其随机访问大数组）：可能导致远低于上述数值
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、空间复杂度
常见空间复杂度
复杂度 通俗理解 例子 O(1) 只用了几个变量，和数据多少无关 交换两个数 O(n) 开了一个一维数组 int arr[100]; O(n²) 开了一个二维数组 int arr[10][10];
怎么算空间复杂度？
口诀：看数组，几个维数几次方
重要：输入数据不算！
空间复杂度只算你额外开的数组，输入数组本身不占额度。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、完整例子对比
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、总结表
你要做的事 时间复杂度 空间复杂度 数组按下标取值 O(1) O(1) 遍历一遍数组 O(n) O(1) 双重循环遍历 O(n²) O(1) 二分查找 O(log n) O(1) 复制一个数组 O(n) O(n) 冒泡排序 O(n²) O(1) 归并排序 O(n log n) O(n)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、记忆口诀
时间看循环，一层 n 两层 n²
空间看数组，一维 n 二维 n²
常数都是 O(1)，输入数据不算它
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、小测验
答案：
* 时间复杂度：O(n²)（双重循环嵌套）
* 空间复杂度：O(n²)（开了二维数组）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
在信奥中，空间限制 128 MiB 时，通常能开的数组大小取决于数据类型和内存开销。
基本结论（C++）
128 MiB ≈ 134,217,728 字节
类型 大小 最多元素个数 int (32位) 4 B 约 3.35 × 10⁷（33,554,432） long long (64位) 8 B 约 1.68 × 10⁷（16,777,216） bool (实际通常1 B) 1 B 约 1.34 × 10⁸（134,217,728） char 1 B 同上 double 8 B 同 long long
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
常见二维数组规模（INT 类型）
* int a[2000][2000]：约 16 MiB ✅ 安全
* int a[5000][5000]：约 100 MiB ✅ 略紧张但可过
* int a[6000][6000]：约 144 MiB ❌ 超限
二维数组极限（int）：约 5700 × 5700
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
注意事项
1. 递归栈空间：递归深度过大（如 10⁵ 层）会额外占用内存，可能导致 MLE 或爆栈。
2. STL 容器开销：
* vector、string 等有少量额外内存（如 vector 约 24 字节的元数据）。
* queue、stack 默认底层是 deque，内存开销比数组大。
* 能用静态数组尽量用静态数组。
3. 多维度数组：总元素数乘以类型大小即可估算。
4. 代码段 + 数据段 + 堆栈：128 MiB 通常指总内存使用，静态数组、全局变量、堆分配（new/malloc）都算在内。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
安全估算
保守上限（int 一维）：3 × 10⁷
保守上限（long long 一维）：1.5 × 10⁷
二维（int）：约 5000 × 5000 以内比较稳
超出这些值，需要仔细计算并留出余量（留给栈、代码、容器开销等）。
