（十七）工作量与存储量

1. 从重复次数计算工作量

设记录数量为 n。遍历一次记录做了 n 轮；遍历完再排序，工作量相加；外层遍历每条记录、内层又比较全部记录，则需要约 n × n 次比较。

# 直接数执行次数：两层完整循环，每轮把次数加一。
n = 4
checks = 0
for left in range(n):
    for right in range(n):
        checks += 1
print(checks)

结果是 16。用 $O(n)$ 表示随记录数线性增长，用 $O(n^2)$ 表示随平方增长。常数次检查记作 $O(1)$ ，常见比较排序按 $O(n\log n)$ 估算；顺序执行的 n 次统计加一次排序，是 n + n\log n，主要增长项仍是 $n\log n$ 。

`n`	`n`	`n log₂ n`，约值	`n²`
1,000	1,000	9,966	1,000,000
10,000	10,000	132,877	100,000,000
100,000	100,000	1,660,964	10,000,000,000

图的横轴与纵轴都使用对数刻度，刻度跨一个数量级表示对应数值乘以十。表和图里的数是操作量估算，不是秒数：一次字典查找、一次字符串比较和一次网络请求耗时不同。先计算重复工作，再用实际程序测量耗时，才能知道慢在哪里。

2. 让保存方式符合操作

操作	CPython 中常见的工作量	解释
列表按下标读取	$O(1)$	直接找到对应位置
列表末尾追加	均摊 $O(1)$	多次追加合看，扩容开销分摊到各次操作
列表中间插入或删除	$O(n)$	后续元素要移动
列表按值查找	$O(n)$	逐项比较直到找到或读完
字典、集合按键查找	平均 $O(1)$	使用散列索引定位候选，再比较键
列表浅拷贝	$O(n)$	把 `n` 个元素引用放到新外层
排序	$O(n\log n)$	比反复扫描全部候选减少重复比较

例如检查 m 个新书名是否已经在含 n 条记录的列表中，逐个执行列表成员检查需要约 $m n$ 次工作。先把已知书名建立成集合，再做这些查询，平均工作量约为 $n+m$ ，同时增加了保存集合的空间。保留顺序和快速查重也可以同时使用列表与集合，分别负责一种需求。

3. 保存结果与逐项处理的空间区别

# 列表保存了全部 n 个结果；生成器把结果逐个交给 sum。
n = 1000
values = [number * number for number in range(n)]
list_total = sum(values)
stream_total = sum(number * number for number in range(n))
print(list_total == stream_total)

列表结果占用随 n 增长的空间；逐项求和不用保存完整的平方列表，但仍然要计算这 n 个平方。节省存储并没有让总计算次数自动减少。

测量时还要分清容器与内部对象：sys.getsizeof(a) 返回对象 a 自身占的字节数；列表内部引用的字符串、整数或子列表，分别还有自己的存储。多个位置指向同一对象时，共享的那份对象只保存了一份。后面进入 NumPy 时，会把对象列表与连续数值数组放在同一组数据上比较。