算法超时判断

核心原则

现代计算机评测系统通常能在 1秒 内执行大约 10⁸ 次基本计算操作。这是我们判断算法是否超时的基准。

---

判断步骤

1. 从题目中寻找两个关键信息：
   • 时间限制： 通常是 1 秒或 2 秒。
   • 最大输入规模 (N)： 这是最重要的信息，例如 “1 <= N <= 100,000”。
2. 确定你的算法的时间复杂度：
   • 分析你所用算法的时间复杂度，并用大O表示法（Big O）写出，如 O(N), O(N log N), O(N²)。
3. 估算总计算量：
   • 将题目给出的 最大输入规模 N 代入你的时间复杂度表达式中。
4. 对比判断：
   • 若 总计算量 < 时间限制 × 10⁸：算法大概率 可以通过。
   • 若 总计算量 > 时间限制 × 10⁸：算法大概率 会超时 (TLE)，需要优化。

---

常见时间复杂度与最大输入规模对应关系 (以1秒为限)

这张表是快速判断的生命线。根据题目给出的N的范围，直接查找你的算法是否可行。

时间复杂度	1秒内能处理的最大输入规模 (N)
O(log N)	任何规模
O(N)	~ 10⁸
O(N log N)	~ 10⁶
O(N²)	~ 10⁴
O(N³)	~ 500
O(2ⁿ)	~ 25
O(N!)	~ 12

---

实战演练

题目条件：
* 输入整数 N，其中 1 <= N <= 200,000。
* 时间限制：1秒。

你的算法选择：

1. 算法A: 时间复杂度为 O(N²)
   • 估算： 将 N 的最大值 200,000 (即 2 × 10⁵) 代入。
   • 总计算量 ≈ (2 × 10⁵)² = 4 × 10¹⁰。
   • 判断： 4 × 10¹⁰ >> 10⁸。必然超时。
2. 算法B: 时间复杂度为 O(N log N)
   • 估算： 将 N 的最大值 2 × 10⁵ 代入。
   • 总计算量 ≈ (2 × 10⁵) × log₂(2 × 10⁵) ≈ 2 × 10⁵ × 18 ≈ 3.6 × 10⁶。
   • 判断： 3.6 × 10⁶ << 10⁸。可以通过。

结论： 面对 N <= 200,000 的数据规模，你必须选择 O(N log N) 或更优的算法，而 O(N²) 的算法是不可行的。