第 4 章：算法复杂度分析 (Complexity Analysis)

在算法竞赛中，评测机给你的时间通常只有 1 秒 (1.0s)。 你的任务不是写出“能算出答案”的代码，而是写出“在 1 秒内算出答案”的代码。

4.1 什么是时间复杂度 (Big O)？

我们不谈复杂的数学定义，只谈**“计算机要做多少次基本运算”**。我们用 $O(\dots)$ 来表示程序在最坏情况下的运算量级。

假设输入数据规模是 $N$（比如数组里有 $N$ 个数）：

• $O(1)$ 常数级： 无论 $N$ 是多少，运行时间不变。

  int a = v[10]; // 访问一次数组
  int b = n * (n + 1) / 2; // 公式计算

• $O(N)$ 线性级： 通常是一个 for 循环。如果 $N=10^5$，大约计算 $10^5$ 次。

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

• $O(N^2)$ 平方级： 通常是双重嵌套循环。

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

  ⚠️ 危险：如果 $N=10^4$，运算量就是 $10^8$（一亿次），这在 1 秒内已经很勉强了。
• $O(\log N)$ 对数级： 非常快！通常出现在二分查找或 Set/Map 操作中。 即便 $N = 10^{18}$（天文数字），$\log_2 N$ 也只有 60 左右。
• $O(N \log N)$ 线性对数级： 这是排序 (sort) 的标准复杂度，也是大多数进阶算法（如分治）的复杂度。它比 $O(N)$ 稍微慢一点点，但远快于 $O(N^2)$。

4.2 黄金法则：1 秒 $\approx 10^8$ 次运算

这是算法竞赛中最重要的经验公式：

现代评测机（C++）在 1 秒内大约能执行 $10^7$ 到 $10^8$ 次基本运算。

• 保守估计：$3 \sim 5 \times 10^7$ 次（绝对安全）。
• 极限操作：$2 \sim 4 \times 10^8$ 次（可能会 TLE，取决于常数大小）。

如何判断你的算法会不会 TLE？ 把题目给出的最大 $N$ 代入你的公式，算出结果，看看有没有超过 $10^8$。

案例演练：

题目给定 $N = 100,000$ ($10^5$)。

1. 你想写冒泡排序 ($O(N^2)$)： 运算量 $\approx (10^5)^2 = 10^{10}$。 $10^{10} \gg 10^8$。结论：绝对 TLE，不用写了，换算法。
2. 你写 std::sort ($O(N \log N)$)： 运算量 $\approx 10^5 \times \log_2(10^5) \approx 10^5 \times 17 \approx 1.7 \times 10^6$。 $1.7 \times 10^6 < 10^8$。结论：稳过，轻松 AC。

4.3 看菜吃饭：根据数据范围猜算法

这是高手解题的第一步。看到 $N$ 的范围，你就大概知道出题人想考什么算法了。

💡 记忆技巧： 只要看到 $N = 10^5$（最常见的范围），哪怕题目再怪，你的解法大概率就是 排序 或者 二分，或者是 $O(N)$ 的贪心。

4.4 空间复杂度：别让内存爆炸

除了时间限制 (Time Limit)，还有内存限制 (Memory Limit)，通常是 128MB 或 256MB。

怎么算？ 主要看你开了多大的数组。

• int 占用 4 字节 (Bytes)。
• long long 占用 8 字节。
• char 占用 1 字节。

常用单位换算： 1 MB $\approx 10^6$ Bytes。 256 MB $\approx 2.5 \times 10^8$ Bytes。

如果你开了一个 int a[N]：

• $N = 10^6$ (一百万)：$4 \text{MB}$ —— 非常安全。
• $N = 10^7$ (一千万)：$40 \text{MB}$ —— 安全。
• $N = 10^8$ (一亿)：$400 \text{MB}$ —— 危险！MLE (Memory Limit Exceeded)。

⚠️ 全局变量 vs 局部变量： 竞赛中建议把大数组开在 main 函数外面（全局变量）。因为局部变量（在函数内部）存放在栈 (Stack) 区，空间很小（通常只有几 MB），开大数组会直接导致 Stack Overflow (爆栈) 运行时错误。

4.5 常见常数优化（玄学优化）

有时候你的复杂度是对的，但还是 TLE 了，可能是“常数”太大。

1. 输入输出：记得用 ios::sync_with_stdio(0); cin.tie(0);（见第 2 章）。
2. 取模运算：取模 (%) 是很慢的操作，尽量减少取模次数。
3. 位运算：乘 2 用 << 1，除 2 用 >> 1，判断奇偶用 & 1（虽然现代编译器会自动优化，但手写位运算在某些题目仍有奇效）。
4. endl vs \n：永远不要在循环里输出 endl，它会强制刷新缓冲区，极其慢。请使用 \n。

🧠 本章小结与练习

核心思想： 动手写代码前，先看 $N$，再算 $O$，最后定方案。

练习作业（思考题）： 假设你在做一个题目，输入 $N$ 个点。

1. 如果 $N=5000$，你需要求任意两点之间的距离，你能用双重循环算出所有距离吗？（计算量 $2.5 \times 10^7$ $\rightarrow$ 可以）
2. 如果 $N=200,000$，你还能用双重循环吗？（计算量 $4 \times 10^{10}$ $\rightarrow$ 绝对不行，必须想 $O(N \log N)$ 或 $O(N)$ 的解法）。

掌握了“算命”的技巧，下一章我们将学习最朴实无华、但也是最容易得分的战术——怎么优雅地暴力破解？