第 21 章　复杂度与 Python 性能¶

配套例题：PIO7、PIO9、BISHI21 来源：S3 day1《栈　队列》开篇的复杂度记号部分

用 C++ 的人算复杂度只需要看数量级，用 Python 的人还得看常数。同样是 \(O(n \log n)\)，C++ 跑 \(10^7\) 轻松，Python 可能就超时了。这一章讲怎么在 Python 里做正确的复杂度估算，以及常数优化的具体手段。

21.1　渐进记号¶

记号	含义	直觉
\(O(f)\)	上界	「不超过」
\(\Omega(f)\)	下界	「不低于」
\(\Theta(f)\)	紧界	「就是这个量级」

竞赛中说「这个算法是 \(O(n \log n)\)」时，通常指的其实是 \(\Theta\)——即紧界。严格区分只在证明下界时才重要。

常见复杂度按增长速度排序：

\[O(1) < O(\log n) < O(\sqrt n) < O(n) < O(n \log n) < O(n \sqrt n) < O(n^2) < O(n^2 \log n) < O(n^3) < O(2^n) < O(n!)\]

21.2　从数据规模反推算法¶

这是竞赛中最实用的技能：看到 \(n\) 的范围，就知道该往哪个复杂度想。

下表按 C++ 1 秒给出，括号里是 Python 的现实可用值（按 20–50 倍慢估算，且牛客给「其他语言」的时限通常是 C/C++ 的 2 倍）：

\(n\) 的范围	目标复杂度	典型算法	Python 现实性
\(n \le 10\)	\(O(n!)\)	全排列枚举	✅ 没问题
\(n \le 20\)	\(O(2^n)\) / \(O(2^n \cdot n)\)	状压枚举、子集 DP	✅ 可以
\(n \le 100\)	\(O(n^3)\)	Floyd、区间 DP	⚠️ \(10^6\) 次循环，勉强
\(n \le 1000\)	\(O(n^2)\)	朴素 DP、\(O(n^2)\) LIS	⚠️ \(10^6\)，可以但别再套常数
\(n \le 10^5\)	\(O(n \log n)\)	排序、堆、线段树、二分	✅ 内置排序很快；手写线段树危险
\(n \le 10^6\)	\(O(n)\) / \(O(n \log n)\)	双指针、前缀和、单调队列	✅ 但必须用内置函数
\(n \le 10^8\)	\(O(n)\) 且常数极小	纯数学、位运算	❌ Python 基本不可能
\(n \le 10^{18}\)	\(O(\log n)\) / \(O(1)\)	快速幂、数学公式、二分	✅ 大整数还是优势

Python 的经验阈值：

纯 Python 的 for 循环，每秒约 \(10^7\) 次简单迭代。
内置函数（sum、sorted、max、min、join）在 C 层跑，每秒约 \(10^8\) 元素。
所以：\(10^7\) 次 Python 层循环 ≈ 1 秒，是危险线；\(10^6\) 是安全线。

核心判断：估算时只数 Python 字节码层面的循环次数，把落到 C 层的操作（sorted、sum、切片、in 一个 set）当成低常数。

21.3　容器操作的复杂度表¶

这张表要背下来。竞赛中大部分 Python TLE 都源于用错了容器。

list¶

操作	复杂度	备注
`a[i]` 读写	\(O(1)\)
`a.append(x)`	\(O(1)\) 均摊
`a.pop()`	\(O(1)\)	从尾部弹
`a.pop(0)`	\(O(n)\)	← 从头弹要整体前移，队列千万别用
`a.insert(i, x)`	\(O(n)\)
`del a[i]`	\(O(n)\)
`x in a`	\(O(n)\)	← 最高频 TLE 原因
`a[i:j]` 切片	\(O(j-i)\)	会复制
`len(a)`	\(O(1)\)	长度是存好的
`a.sort()`	\(O(n \log n)\)	Timsort，C 实现，很快
`min/max/sum(a)`	\(O(n)\)	C 层循环
`a.reverse()` / `a[::-1]`	\(O(n)\)	前者就地，后者复制
`a.count(x)` / `a.index(x)`	\(O(n)\)

deque（`collections.deque`）¶

操作	复杂度
`append` / `appendleft`	\(O(1)\)
`pop` / `popleft`	\(O(1)\)
`d[i]` 随机访问	\(O(n)\) ← 双向链表结构，不能当数组用

选型：需要两端操作 → deque；需要随机下标访问 → list。两者都要 → 重新想算法。

dict / set¶

操作	平均	最坏
`d[k]` 读写、`k in d`	\(O(1)\)	\(O(n)\)（哈希冲突）
`s.add(x)`、`x in s`	\(O(1)\)	\(O(n)\)
遍历	\(O(n)\)

最坏情况在竞赛中几乎不会自然出现，但存在被专门构造数据卡的可能—— 出题人可以构造大量哈希值相同的整数键。防御手段见 36-哈希与字符串哈希。

str¶

操作	复杂度
`s[i]`	\(O(1)\)
`s + t`	\(O(len(s) + len(t))\) ← 字符串不可变，每次都新建
`s in t`	\(O(nm)\) 最坏，实际有优化
`"".join(list)`	\(O(总长度)\)

循环拼接字符串是 \(O(n^2)\)：

# ❌ O(n²)：字符串不可变，每次 += 都要新建一个更长的字符串并整体复制
s = ""
for x in a:
    s += str(x)

# ✅ O(n)：join 先量好总长度，只分配一次、只复制一次
s = "".join(map(str, a))

heapq¶

操作	复杂度
`heappush` / `heappop`	\(O(\log n)\)
`h[0]` 看堆顶	\(O(1)\)
`heapify(list)`	\(O(n)\) ← 不是 \(O(n\log n)\)

21.4　常数优化的具体手段¶

当算法复杂度已经正确、但还是 TLE 时，按下面的顺序试。

1. 把逻辑装进函数¶

CPython 里局部变量走数组下标（LOAD_FAST），全局变量走字典查找（LOAD_GLOBAL）。 这一条通常能带来 20%–30% 提速，且几乎零成本：

import sys


def main():
    ...              # 所有逻辑写这里：函数体内的名字都是局部变量


main()               # 顶层只留这一句调用

2. 把常用的全局名绑成局部名¶

循环内反复访问 math.gcd 要做两次查找（模块 + 属性）。提前绑定：

from math import gcd
_gcd = gcd                      # 绑成局部名：循环里省掉一次全局字典查找
for i in range(n):
    g = _gcd(g, a[i])           # 写 math.gcd 的话每轮要查「模块 + 属性」两次

同理，循环里用到的 append 可以提前取出来：

res = []
push = res.append               # 方法只取一次；每轮的 res.append 属性查找就省掉了
for x in a:
    push(x * 2)                 # 循环次数越多，这一改的收益越明显

3. 把循环下沉到 C 层¶

这是 Python 优化的核心思路：不是让循环跑得更快，而是让循环消失。

# 慢：Python 层循环，每次迭代都要走一遍字节码分派
s = 0
for x in a:
    s += x

# 快：同样是 n 次加法，但循环本身在 C 里跑，没有字节码开销
s = sum(a)

常用的「下沉」武器：

想做的事	Python 循环	C 层写法
求和	`for` 累加	`sum(a)`
最值	`for` 比较	`max(a)` / `min(a)`
转换类型	`[int(x) for x in a]`	`list(map(int, a))`
过滤	`[x for x in a if f(x)]`	`list(filter(f, a))`
前缀和	`for` 累加	`list(accumulate(a))`
计数	`dict` 手动累加	`Counter(a)`
拼接	`+=`	`"".join(...)`
排序	手写	`sorted(a)`
判存在	遍历	`x in set`
二分	手写	`bisect_left`

map 比列表推导式快的前提是函数本身是 C 实现（如 int、str）。如果是自己写的 Python 函数，map 反而可能更慢，因为每次调用都有开销。这时列表推导式更好。

下沉只改常数，不改渐进复杂度。 两种算法的复杂度差一个 \(\log\) 时，C 层的常数优势通常补不回来：多重背包的二进制拆分每轮都是 C 层整段处理，极限数据实测 80.1 秒；纯 Python 层的单调队列实测 14.9 秒，快 5.4 倍。先比复杂度、再谈常数，见 101-背包问题 §101.5。

4. 输入输出¶

见 20-输入输出处理。一句话：读用 sys.stdin.buffer.read().split()，写用 sys.stdout.write("\n".join(...))。 \(10^5\) 行的规模，光这一条就能从 TLE 变 AC。

5. 数组用 list 而不是 dict¶

小值域下用 list 当数组，比 dict 快 2–3 倍（省掉哈希计算）：

cnt = [0] * (MAXV + 1)          # 值域已知且不大：下标直接寻址，不算哈希
cnt = defaultdict(int)          # 值域未知或稀疏：这时才值得付哈希的代价

6. 避免不必要的对象创建¶

# 每轮都要打包一个 (下标, 值) 元组再解包
for i, x in enumerate(a):
    ...

# 用不到下标就别要它，省掉这次打包与解包
for x in a:
    ...

但不要为此牺牲可读性——enumerate 的开销很小，只在最内层热循环才值得计较。

21.5　什么时候该放弃某个做法¶

有些在 C++ 里天经地义的写法，在 Python 里就是不可行的。识别它们能省下大量调试时间。

做法	C++	Python	替代方案
手写线段树，\(n = 10^5\)，\(q = 10^5\)	✅	⚠️ 约 \(4 \times 10^6\) 次 Python 递归，极险	用树状数组（常数小 5 倍）或分块
手写线段树，\(n = 10^6\)	✅	❌	换算法
递归 DFS，深度 \(10^5\)	✅	⚠️ 要开线程栈	改迭代
\(O(n^2)\)，\(n = 5000\)	✅	❌ \(2.5\times10^7\) 次纯循环	找 \(O(n\log n)\) 做法
埃氏筛 \(10^7\)	✅	⚠️ 用 `bytearray` 切片赋值可行	见下
大整数运算 \(10^5\) 位	需手写高精度	✅ 原生支持	Python 反而占优

埃氏筛的 Python 写法¶

朴素的双重循环筛 \(10^7\) 必然超时，但用切片赋值可以把内层循环下沉到 C：

def sieve(n):
    is_p = bytearray([1]) * (n + 1)       # 先全标成素数；1 字节一格，比 list 省内存
    is_p[0:2] = b"\x00\x00"               # 0 和 1 不是素数
    for i in range(2, int(n ** 0.5) + 1):  # 筛到根号 n 为止：更大的因子必配一个更小的
        if is_p[i]:                       # 轮到 i 时还没被划掉 ⇒ i 是素数
            # 从 i*i 起步：比 i*i 小的 i 的倍数，都已被更小的素因子划掉过
            # 关键：切片步长赋值，内层循环在 C 层完成；bytearray(k) 是 k 个 0，即「标为合数」
            is_p[i * i::i] = bytearray(len(is_p[i * i::i]))
    return is_p

bytearray 比 list 省内存（1 字节 vs 8 字节指针），切片步长赋值把「标记所有 \(i\) 的倍数」这个 \(O(n/i)\) 循环整个交给 C。这是「让循环消失」思路的典型应用，详见 80-数论基础。

21.6　例题¶

PIO7 / PIO9：为什么必须用 token 流¶

PIO7：\(t \le 10^5\) 组，\(\sum n \le 10^5\)。 PIO9：\(t \le 10^5\) 组，\(\sum n \cdot m \le 10^6\)。

这两题算法上毫无难度（就是求和），唯一的考点就是读入速度。

用 input() 逐行读，PIO9 要执行 \(10^5\) 次 input() 加 \(10^6\) 次 int()，前者的解释器开销就足以 TLE。换成：

# [片段]
data = sys.stdin.buffer.read().split()

一次系统调用读完全部输入，split() 在 C 层完成分词。实测在这个规模上是十几倍的差距。题解见 solutions/PIO7.py、solutions/PIO9.py。

BISHI21 【模板】排序¶

排序模板题。

考点是「不要手写排序」：

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
a = sorted(map(int, data[1:1 + n]))       # sorted 直接吃迭代器，省掉一个中间列表
sys.stdout.write(" ".join(map(str, a)) + "\n")   # 一次写出，不在循环里 print

Python 的 sorted 是 Timsort，C 实现，\(n = 10^5\) 时约 0.02 秒。手写快排在 Python 里要慢 50 倍以上，而且有被卡成 \(O(n^2)\) 的风险。

在 Python 里，手写排序算法只有教学意义，没有实战意义—— 但你仍然需要理解它们的原理，因为面试会问，而且归并排序的分治思想是求逆序对的基础。见 40-排序。

21.7　本章速查¶

判断	结论
Python 层循环速度	约 \(10^7\) 次/秒，\(10^6\) 是安全线
内置函数速度	约 \(10^8\) 元素/秒
估算方法	只数 Python 字节码层的循环次数
`list.pop(0)`	\(O(n)\)，队列用 `deque`
`deque[i]`	\(O(n)\)，随机访问用 `list`
`x in list`	\(O(n)\)，改用 `set`
循环拼字符串	\(O(n^2)\)，改用 `join`
`heapify`	\(O(n)\)，不是 \(O(n\log n)\)

优化手段	收益
逻辑装进函数	20%–30%
全局名绑成局部名	5%–15%
循环下沉到 C 层	数倍到数十倍 ← 同复杂度下首选；救不了复杂度本身
快速 IO	大输入下十几倍
`list` 代替 `dict` 当数组	2–3 倍

第 21 章 复杂度与 Python 性能¶

21.1 渐进记号¶

21.2 从数据规模反推算法¶

21.3 容器操作的复杂度表¶