数据范围与复杂度直觉

本节学会什么

• 从题目数据范围估计可接受的循环层数
• 区分线性扫描和两层循环的工作量
• 在写代码前写下预期的时间复杂度

为什么需要它

同一题的答案可能既能用一层循环求出，也能用三层循环“硬算”出来。小样例看不出差别，评测数据一大，后者就会 TLE。数据范围是题目给你的重要提示：它告诉你程序最多能做多少次近似操作。

最小可运行示例

读入 n 个数并求最大值，只需要每个数看一次：

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

这段循环大约执行 n 次，记作 O(n)。若要把每一对元素都比较一次，就会有两层循环：

for (int i = 0; i < n; i += 1) {
    for (int j = i + 1; j < n; j += 1) {
        // 比较 a[i] 和 a[j]
    }
}

它大约执行 n * n / 2 次，记作 O(n^2)。当 n = 100000 时，两者的数量级差异已经非常大。

关键过程与易错点

• n <= 20 时，可以考虑 O(2^n) 的枚举；这类做法会在后面的搜索中出现。
• n <= 10^3 时，通常可以考虑 O(n^2) 的两层循环。
• n <= 10^5 时，通常需要 O(n) 或 O(n log n) 的方法，而不是双重循环。
• 这些是估算，不是硬性定律。测试组数、每次循环中的工作量、常数和机器速度都会影响实际时间。
• 看范围时不要只看单个 n：若有 T 组数据，应一起估算 T 次处理的总工作量。
• 写代码前先在草稿上标出主要循环，并写下预期复杂度。代码完成后再检查它是否与范围相配。

动手检查

分别估算下列循环的执行次数：n = 1000 的两层完整循环，以及 n = 100000 的一层循环。无需精确到每一步，只要比较数量级。

找一道已经做过的数组题，在题面上圈出最大数据范围。写下自己的程序有几层与 n 有关的循环，以及它大约是 O(n) 还是 O(n^2)。

立即练习