看数据规模挑算法

先看数据范围

到这一课为止，你学过的算法族已经不少了：哈希、树、堆、并查集、图和搜索、二分答案、贪心、动态规划。可真正坐在考场上，最难的一步往往不是写代码，而是第一分钟不知道这题该往哪个方向想。

有一个线索一直被放在题面最显眼的地方，很多人却不看它——数据范围。

题目说 n \le 10^5，这不是在描述数据，是在告诉你该用什么算法。范围到 10^5，平方级的做法就已经跑不完了；范围到 10^3，平方级甚至三次方级都还能活。范围到 20 上下，多半是在请你枚举子集。

这一课要做的，是把这条对应关系变成条件反射：先读范围，算出复杂度上限，再回头挑算法族。先挑算法再回头看范围，顺序反了。

本机一秒能跑多少次

要把范围和复杂度对上，得先知道一秒能跑多少次基本操作。这是个实测值，不是通用常数。

量法很简单：拿一个空转的加法循环，跑几个不同的 n，用 time.perf_counter() 卡住前后，把总用时除以 n 就是「每次循环多少纳秒」。这段代码放在本课最后的练习里，你要在自己这台机器上跑一遍，下面的数是本机的。

本机实测（每次跑都会有些浮动，看量级就行）：

注意第三列基本不随 n 变——16.6、19.0、19.7、19.4，都在 20 纳秒上下。这说明一次循环的开销是个常数，所以总用时和 n 是成正比的。如果这一列随 n 明显变大或变小，说明你量错了（多半是循环体里干了别的事，或者机器正在忙别的）。

每次循环大约 20 纳秒，反过来说——每秒约五千万次。

这正好跟第 2 课给的那把尺子对上了（那一课定的是「每秒约 5 \times 10^7 次」）。两处是各自独立量出来的，量到同一个数，所以后面就用这把尺子算。

范围换算成复杂度上限

有了尺子，就能反推：一秒的预算下，每种复杂度的 n 最多能到多少。

import math

RULER = 5 * 10 ** 7


def steps_log10(name, k):
    """第 name 种复杂度在规模 k 上的「步数的常用对数」。

    只算对数、不真把那个数算出来——O(2^n) 在 k 大时是个天文数字，
    真去构造它会撑爆内存（k = 5*10^8 时是 10^150514997 这个量级）。
    """
    if name == 'O(n)':
        return math.log10(k)
    if name == 'O(n log2 n)':
        return math.log10(k) + math.log10(max(1.0, math.log2(k)))
    if name == 'O(n^2)':
        return 2 * math.log10(k)
    if name == 'O(n^3)':
        return 3 * math.log10(k)
    return k * math.log10(2)


def fits(name, k):
    return steps_log10(name, k) <= math.log10(RULER)


print(f'   尺子：每秒 {RULER:,} 步（第 2 课那把）')
print()
print('   复杂度        1 秒内的 n 上限        跑到 10^8 步要多久')
for name in ('O(n)', 'O(n log2 n)', 'O(n^2)', 'O(n^3)', 'O(2^n)'):
    n = 1                                    # 先翻倍逼近，再二分
    while n * 2 <= 10 ** 9 and fits(name, n * 2):
        n *= 2
    lo, hi = n, min(n * 2, 10 ** 9)
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if fits(name, mid):
            lo = mid
        else:
            hi = mid - 1
    big = steps_log10(name, 10 ** 8)
    if big >= 15:
        secs = f'约 10^{int(big - math.log10(RULER))} 秒'
    else:
        secs = f'{10 ** (big - math.log10(RULER)):.4g} 秒'
    print(f'   {name:<12} {lo:>16,}        {secs:>16}')

   尺子：每秒 50,000,000 步（第 2 课那把）

   复杂度        1 秒内的 n 上限        跑到 10^8 步要多久
   O(n)               50,000,000                     2 秒
   O(n log2 n)         2,361,678                 53.15 秒
   O(n^2)                  7,071                约 10^8 秒
   O(n^3)                    368               约 10^16 秒
   O(2^n)                     25         约 10^30102991 秒

上一段那个 steps_log10 值得看一眼：它只算对数。O(2^n) 在 n = 10^8 时的步数是 2^{10^8}，这个数有约三千万位十进制——真把它算出来，内存直接就没了。所以这里全程在对数域里比大小，只在最后要显示秒数时把指数取出来。约 10^30102991 秒 这个说法读作「这个量级」，别当精确值。

把中间那一列记住，这一课就学完了大半：

反过来读同一张表，就是从范围反查：

• 范围 n \le 10^5 → 只能上 O(n) 或 O(n \log n)。看到「平方级」就知道思路错了。
• 范围 n \le 10^3 → O(n^2) 可以，O(n^3) 在边界上（10^9 步要几十秒，不行）。
• 范围 n \le 20 上下 → 出题人就是在请你枚举子集或者状压，别硬找多项式做法。

同一道题的三个版本

「复杂度」这三个字听起来抽象，用一道题摆出来就具体了。最大子段和：给一串数，求和最大的那一段连续子序列。

这道题有三个写法，答案完全一样，步数差得很远：

def max_sum_cubic(a):
    """O(n^3)：把左右端点全试一遍，中间再累加一遍。返回 (答案, 内层步数)。"""
    n = len(a)
    best = a[0]
    steps = 0
    for i in range(n):
        for j in range(i, n):
            s = 0
            for k in range(i, j + 1):
                s += a[k]
                steps += 1
            if s > best:
                best = s
    return best, steps


def max_sum_quadratic(a):
    """O(n^2)：固定左端，右端往外扩时顺手累加。"""
    n = len(a)
    best = a[0]
    steps = 0
    for i in range(n):
        s = 0
        for j in range(i, n):
            s += a[j]
            steps += 1
            if s > best:
                best = s
    return best, steps


def max_sum_linear(a):
    """O(n)：要么接上前面，要么从自己重新开始。"""
    best = cur = a[0]
    steps = 1
    for x in a[1:]:
        cur = x if cur < 0 else cur + x
        if cur > best:
            best = cur
        steps += 1
    return best, steps


A = [(-1) ** i * (i % 17) for i in range(100)]
print(f'   n = 100 时三个版本给出的答案一致吗: '
      f'{max_sum_cubic(A)[0] == max_sum_quadratic(A)[0] == max_sum_linear(A)[0]}'
      f'（都是 {max_sum_linear(A)[0]}）')
print()
print('   规模     O(n^3) 步数     O(n^2) 步数     O(n) 步数')
for n in (50, 100, 200, 400):
    a = [(-1) ** i * (i % 17) for i in range(n)]
    print(f'   {n:>6}   {max_sum_cubic(a)[1]:>12,}   {max_sum_quadratic(a)[1]:>12,}   '
          f'{max_sum_linear(a)[1]:>10,}')
b1 = max_sum_cubic([0] * 200)[1] / max_sum_cubic([0] * 100)[1]
b2 = max_sum_quadratic([0] * 200)[1] / max_sum_quadratic([0] * 100)[1]
b3 = max_sum_linear([0] * 200)[1] / max_sum_linear([0] * 100)[1]
print(f'   n 从 100 翻到 200：三版的步数分别变成 {b1:.1f} 倍、{b2:.1f} 倍、{b3:.1f} 倍')

   n = 100 时三个版本给出的答案一致吗: True（都是 24）

   规模     O(n^3) 步数     O(n^2) 步数     O(n) 步数
       50         22,100          1,275           50
      100        171,700          5,050          100
      200      1,353,400         20,100          200
      400     10,746,800         80,200          400
   n 从 100 翻到 200：三版的步数分别变成 7.9 倍、4.0 倍、2.0 倍

最后的倍数就是复杂度的指纹。 规模翻一倍，三次方版涨约 8 倍（量到 7.9 倍），平方版涨约 4 倍（量到 4.0 倍），线性版涨 2 倍（量到 2.0 倍）。

这不是巧合，是定义：O(n^3) 里的 3 就是说「n 翻倍、步数翻 2^3 倍」。所以你量出来的倍数，反过来能告诉你这段代码是什么复杂度——比自己数循环层数可靠，因为循环不一定规整。

顺带看一件很值钱的事：n = 100 时三个版本都是 24，答案一样。区别只在步数——171{,}700 对 5{,}050 对 100。正确性上它们等价，取舍全在能不能跑得完。

范围决定你用哪一版

上表是步数，换成时间更直观。下面这张是同一批函数在本机跑出来的本机实测秒数：

n = 800 时三次方版要 1.5 秒——已经超了。而它离 10^5 还差着两个数量级。

按复杂度把 n = 800 这一行外推（每翻倍：三次方涨 8 倍、平方涨 4 倍、线性涨 2 倍）：

n = 10^5 那一行是最该看的一行：

• 三次方版要 300 万秒，约 35 天。
• 平方版要 113 秒，还是超，但已经不是天文数字了——这说明「差一个数量级」比「完全不可能」更危险，因为它看起来还能等。
• 线性版要 0.0036 秒。

所以同一道最大子段和：

• 数据范围给 n \le 100：三个版本随便挑，写三次方版还更不容易错。
• 数据范围给 n \le 3000：三次方版不行了，平方版够用。
• 数据范围给 n \le 10^5：只能用线性版。

题目没变，范围变了，答案就该换写法。 这也解释了省赛为什么爱出「同一道题、不同数据范围」的一组题——那是在考你会不会读范围。

多组测试的陷阱

有一种情况会让「范围反查」失灵，而且非常常见：多组测试数据。

n = 1000 这个范围，按上面的表看，平方级随便写（10^6 步，跑一下 0.01 秒）。但如果题面还有一句「共 10^5 组测试数据」呢？

n = 1000
per_case = max_sum_quadratic([(-1) ** i * (i % 17) for i in range(n)])[1]
print(f'   n = {n} 时，O(n^2) 一组的步数: {per_case:,}')
print()
print('   组数          总步数')
for cases in (1, 10, 100, 1000, 100000):
    print(f'   {cases:>8,}   {per_case * cases:>18,}')
print()
print(f'   一组的 n = {n} 看着很小，10^5 组一乘就是 {per_case * 100000:,} 步。')

   n = 1000 时，O(n^2) 一组的步数: 500,500

   组数          总步数
          1              500,500
         10            5,005,000
        100           50,050,000
      1,000          500,500,000
    100,000       50,050,000,000

   一组的 n = 1000 看着很小，10^5 组一乘就是 50,050,000,000 步。

一组的 n = 1000 看着很小，10^5 组一乘就是 5 \times 10^{10} 步。

拿尺子一除：5 \times 10^{10} \div (5 \times 10^7) = 1000 秒。判分给每道题通常只有一两秒。

本机实测同一件事：n = 1000 时平方版跑一组要 0.0120 秒，10^5 组就是 1200 秒——跟上面的估算对得上。

所以读范围时要读的是「一组的 n」乘「组数」的那个总量，不是单看 n。题目写「n \le 1000，T \le 10^5」的时候，真正的规模是 10^8。

问法也在提示算法

范围之外，问法是第二条线索。同一个数据规模下，「求最大值」「求方案数」「问可不可达」指向的算法族完全不同。

下面这张表把学过的都收进来了：

一张可查的题型表

把两条线索合起来用，就成了一个先范围、后问法的查表流程：

1. 读范围，算出复杂度上限。 上限是 O(n \log n) 还是 O(n^2)？这一步就能划掉一大半候选。
2. 读问法，缩小到两三个算法族。 用上一节那张表。
3. 看候选里哪几个的复杂度在上限之内。 都行的，挑实现最简单的那个。
4. 写之前先想清楚怎么验。 上一课那套：小数据对拍、反例最小化。

第 3 步里藏着一个很多人会做反的选择：几个候选都跑得完的时候，要挑最好写的那个，不是最快的那个。

原因是，写错的代价远大于慢一点点的代价。一个 O(n \log n) 的正确解，和一个「理论上 O(n) 但边界漏了」的解，前者拿满分，后者拿零分——而复杂的写法边界就是更多。

这一课用到的判断

• 先读范围，再想算法。 范围是题面给你的第一句话，也是最有用的一句话。
• 本机每秒约 5 \times 10^7 次（本机实测，换机器会差几倍）。一秒的上限：O(n) 到 5 \times 10^7、O(n \log n) 到 2.4 \times 10^6、O(n^2) 到 7 \times 10^3、O(n^3) 到 370、O(2^n) 到 26。
• 量出来的增长倍数就是复杂度的指纹：翻倍后涨 8 倍是三次方、4 倍是平方、2 倍是线性。这比数循环层数可靠。
• 同一道题不同范围就是不同的题。 最大子段和在 n \le 100 上写三次方版没问题，在 n \le 10^5 上只能用线性版，而三版答案完全一样（实测都是 24）。
• 多组测试要乘起来看。 「n \le 1000、T \le 10^5」的真实规模是 10^8。实测 n = 1000 平方版一组 0.0120 秒，10^5 组是 1200 秒。
• 「差一个数量级」比「完全不可能」更危险。 平方版在 n = 10^5 上要 113 秒——不是 35 天，看起来还能等，于是容易被放过去。
• 所有上限都是量级参考，不是判决线。 换 CPU、换写法、用不用内置函数都能差好几倍。取舍靠量级，卡线要靠实测。
• 候选都跑得完时，挑最好写的，不是最快的。 写错的代价大于慢一点点的代价，而复杂写法的边界更多。
• 问法只是线索。 「重量」把「合并果子」指向背包是实测过的假阳性。表用来缩方向，题意要自己读懂。

import time


def loop_cost(n):
    s = 0
    for i in range(n):
        s += i
    return s


for n in (10 ** 5, 10 ** 6, 10 ** 7, 10 ** 8):
    t0 = time.perf_counter()
    loop_cost(n)
    dt = time.perf_counter() - t0
    print(f'   n = {n:>11,}   用时 {dt:6.3f} s   每次循环 {dt / n * 1e9:5.1f} ns')

• 《算法竞赛进阶指南》题型与复杂度对应书 · 范围与算法的对应关系（具体章节待核实）
• OI Wiki · 复杂度竞赛里常用的复杂度分析与常见量级
• 第 2 课：同一道题，两种写法本课那把尺子就是那一课定的
• 第 22 课：二分答案：猜一个再验一遍「让最大值最小」这类问法该去的地方
• 第 24 课：动态规划：把重复计算记下来「方案数」与「最优值」指向的那一族
• 第 27 课：实验三：让助手推荐并验证让程序替你判算法族，以及它为什么会误判