同一道题，两种写法

上一课结尾留了一句话：从这一课起，把「看数据范围、估操作次数、定复杂度上限」练成一套固定动作。这一课就把它做成一个能反复使用的记号。

先回到那个上一课已经踩过的坑。样例只有三五个数，跑起来永远飞快，所以「样例通过」对「会不会超时」几乎没有预测力——真正的问题在评测机用最大数据跑你代码的那一刻才暴露。蓝桥杯每道题都写明数据范围与时限，能不能过，几乎在你选定写法的瞬间就定了。这一课要做的，是把「这种写法会不会超时」这个判断，提前到动手写代码之前。判断之前照例先想清楚输入和输出是什么——这一步上一课刚走过，这里不再展开，但它永远是第一步。

先数基本操作

同一个算法在不同机器上跑，速度会有差别，实际用时难以在理论上计算，实测又麻烦。所以衡量算法效率时，通常数的是算法需要执行的基本操作数量：在普通计算机上，加减乘除、访问变量、给变量赋值，都可以算作一次基本操作。

时间复杂度衡量的，是这个数量随数据规模增长的趋势：数据规模越大，算法用时越长，但最重要的不是某个规模下的用时，而是用时随规模增长的趋势。为什么看趋势，而不是看某一次的用时，有两条理由：

• 现代计算机每秒能处理数亿乃至更多次基本运算，我们处理的数据规模通常很大。以来源里的对比为例：用时 100n 的算法一秒能处理数百万规模，用时 n^2 的算法只能处理数万规模——数据规模一大，两档的差距立刻拉开。
• 不同基本操作的实际用时不同，加减远快于除法。只看操作次数、忽略它们之间的差别，能消除这种影响。

上面「每秒数亿次」是来源里针对编译型语言的一般说法，它的例子是 C++；Python 每执行一条语句要拆成很多条底层运算，实测速率会慢一截。Python 这边该是多少，稍后用 timeit 单独量出来，不套用这个数字。

补充一点：实际用时也跟输入内容有关，所以复杂度分最坏与平均两类。竞赛里输入可以在数据范围内任意给定，为了保证任何数据都能过，我们只关心最坏时间复杂度。

大 O 记号

「增长趋势」是个模糊的说法，需要一套记号把它写下来。这套记号叫渐近符号：它忽略一个函数里增长较慢的部分和各项的系数（系数在复杂度分析里通常叫「常数」），只保留决定增长趋势的那部分。

记号的名字有来历。大 O 的 O 来自希腊字母 Omicron，字形与拉丁字母 O 相同；小 o 同源。一个记忆法：含等于用大写、不含用小写；相等是 \Theta、小于（上界）是 O、大于（下界）是 \Omega。竞赛里最常用的是 O，因为我们关心的是程序用时的上界。

形式化定义是这样：设 f(n) 与 g(n) 是定义在正整数上的函数，f(n) = O(g(n)) 当且仅当存在正常数 c 与 n_0，使得对一切 n \ge n_0，都有 0 \le f(n) \le c \cdot g(n)。

翻译成普通话：当 n 足够大之后，f(n) 的增长不超过 g(n) 的某个常数倍。所以 O(g(n)) 说的是「增长趋势的上界」，不是一个精确值。例如 3n^2 + 5n - 3 = O(n^2)——当 n 足够大，3n^2 + 5n - 3 始终不超过 4n^2，取 c = 4 即可。

常数与数量级

渐近符号丢掉系数和低阶项，带来一条最容易踩的判断：O(2n) 与 O(n) 是同一档，O(100n) 与 O(n) 也是同一档。它们差的只是常数倍，而常数倍在数量级面前可以忽略——n 放大十倍，2n 与 100n 也都只放大十倍，增长趋势一样。真正分档的是最高阶项：

每个记号都只保留最高阶项、丢掉系数：2n^2 + 100n 里的 100n 是低阶项、2 是系数，都不出现在记号里。

反过来，哪些量算常量也要分清。一段固定跑 N = 100000 次的循环，如果这个 N 不被看作输入规模，它的复杂度就是 O(1)。判断的关键是「哪个量是输入规模」：所有与输入规模无关的量，计算复杂度时都当作 1 处理。

从代码里读出复杂度

有了记号，下一步是从一段代码里把它读出来。规则和循环的嵌套层数直接对应：

• 没有循环、或只做固定次数操作，是 O(1)；
• 一层循环跑 n 次，是 O(n)；
• 两层循环嵌套、各跑 n 次，是 O(n^2)。

先看上一课的求和题。写法一是循环：

n = int(input())
total = 0
for i in range(1, n + 1):
    total += i
print(total)

循环执行 n 次，每次做一次加法、一次赋值，基本操作次数随 n 线性增长，写做 O(n)。写法二是公式：

n = int(input())
print(n * (n + 1) // 2)

不管 n 多大，都只做固定几次乘除，操作次数不随 n 增长，写做 O(1)。

再看一道题：数一数 1 到 n 之间有多少个无序数对 (i, j)，满足 i < j。最直接的写法是两层循环：

count = 0
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        count += 1
print(count)

内层循环一共跑了 (n-1) + (n-2) + \dots + 1 次，也就是 \dfrac{n(n-1)}{2} 次，写做 O(n^2)。同一道题的另一种写法是公式：从 n 个数里选两个，结果是 \dfrac{n(n-1)}{2}，直接算：

n = int(input())
print(n * (n - 1) // 2)

这是 O(1)。同一道题，O(n^2) 与 O(1)，差距比上一题更大：n 每放大十倍，前一种写法慢一百倍。

两层循环是竞赛里最常见的超时来源。很多两层循环都能降到一层，那是后面课程的主题（比如区间求和用前缀和，一层预处理加一步查询）；这里先记住：写出循环之前，先数它套了几层。

数据规模反推上限

有了 O 记号，再加一把本机实测的「每秒能做多少次基本操作」的尺子，就能把数据范围翻译成「这道题最多能接受哪档复杂度」；反过来，看数据范围，也能反推该用哪档写法。

上一课已经量过：这台机器（Python 3.14 的 free-threading 构建）跑最简单的累加循环，约 189 毫秒跑完 10^7 次，折合每秒约 5\times10^7 次。这比上面「每秒数亿次」的通用说法慢一截，因为那说的是编译型语言的量级，Python 每执行一条语句要拆成很多条底层运算。这个数字只属于这台机器、这个 Python 版本，换一台要重新量——它就是本课的尺子。假设一秒约做 5\times10^7 次基本操作，把各档复杂度在 1 秒内能处理的最大 n 解出来：

还有两档现在先认识名字：O(\log n) 是每步把范围砍半，比线性还快，二分那课展开；O(2^n) 是把每种可能都枚举一遍，只能处理 n 二十几，搜索那课常见。排序这类算法常是 O(n\log n)，介于 O(n) 与 O(n^2) 之间。

这张表的用法分正反两个方向：

• 正向：拿到数据范围 n，先估自己写法的复杂度，再查表看它在时限内能不能跑完。
• 反向：拿到数据范围 n，先由 n 定出「可接受的复杂度上限」，再去想符合这档的写法。比如 n = 10^9 只可能是 O(1) 或 O(\log n)，连 O(n) 都跑不完。

现在回头看开头的结论为什么成立：「样例通过」没有预测力，是因为样例的数据规模离上限差着好几个数量级——样例跑得动，只说明最小那一档能过。判断会不会超时，要看的是题目给出的最大数据范围落在表的哪一行。配套项目「AI 刷题助手」在推荐候选算法时，第一步也正是这样：按题目数据范围，先把复杂度不达标的那批算法筛掉。

空间复杂度

类似的，算法使用的空间随规模增长的趋势叫空间复杂度。通常不计输入本身占的空间，只算算法额外开的那部分。

上面两道题正好是两面：求和公式版与数对公式版都不额外开数组，空间复杂度 O(1)；而有些算法会用一份 O(n) 大小的额外空间，把时间从 O(n^2) 降到 O(n)——这种「空间换时间」是后面课程的主题，眼下先记住时间与空间常常可以互换这一条。

练习

import timeit

def pair_loop(n):
    count = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            count += 1
    return count

def pair_formula(n):
    return n * (n - 1) // 2

for n in (10**3, 10**4):
    t = min(timeit.repeat(lambda: pair_loop(n), number=1, repeat=3))
    print(n, f"{t:.3f} 秒")

这一课用到的 Python

课程讲到后面，这些「数基本操作、写 O 记号、反推上限」的动作会一遍遍重复，直到成为拿到题就自动做的第一步。

• OI Wiki · 复杂度复杂度定义、渐近符号（O/Θ/Ω）与最坏/平均复杂度，本课「数基本操作」与 O 的定义出自这里
• Python 官方文档 · timeit性能测量的官方用法，练习里的实测照它写
• 《Python 编程：从入门到实践（第 2 版）》第 4 章 操作列表用循环处理一批数据的写法，本地教材