渐近分析说明输入变大时的增长趋势，实测说明某个环境、某组数据与某种实现的表现。两者需要一起使用。一次小输入跑得快，不能证明增长率；理论复杂度相同，也可能因对象分配、局部性和解释器开销产生明显差距。
先规定比较的工作量
下面比较列表与集合的重复成员查询。两者查询同一批值，先确认命中数量相同，再用 perf_counter 多次测量。集合在计时外建立，所以结果只反映“已有结构上的查询”，不包括建集合的时间；一次性查询时应把构建成本也加入比较。
import random
import statistics
import time
def reservoir_sample(stream, k, rng):
if k < 0:
raise ValueError('k must be non-negative')
sample = []
if k == 0:
return sample
for i, item in enumerate(stream, 1):
if i <= k:
sample.append(item)
else:
position = rng.randrange(i)
if position < k:
sample[position] = item
return sample
def vertex_cover_2approx(edges):
if any(a == b for a, b in edges):
raise ValueError('this example requires no self-loops')
cover = set()
for a, b in edges:
if a not in cover and b not in cover:
cover.update((a, b))
return cover
def membership_benchmark(n, repeats=5):
if n <= 0 or repeats <= 0:
raise ValueError('n and repeats must be positive')
rng = random.Random(20)
values = [rng.randrange(2 * n) for _ in range(n)]
queries = [rng.randrange(2 * n) for _ in range(min(n, 300))]
members = set(values)
expected = sum(query in values for query in queries)
result = {}
for label, container in [('list', values), ('set', members)]:
samples = []
for _ in range(repeats):
start = time.perf_counter()
actual = sum(query in container for query in queries)
samples.append(time.perf_counter() - start)
if actual != expected:
raise AssertionError('implementations disagree')
result[label] = {'hits': expected, 'median_seconds': statistics.median(samples)}
return result
if __name__ == '__main__':
print(reservoir_sample(iter(range(100)), 5, random.Random(20)))
print(sorted(vertex_cover_2approx([(0, 1), (1, 2), (2, 3)])))
for size in (128, 512, 2048):
print(size, membership_benchmark(size))
运行时会打印当前机器的计时值，正文不预设某个速度倍数。记录Python版本、输入规模、查询分布、随机种子和重复次数后，才能复现这次实验。最小值可帮助观察较少调度干扰的下界，中位数反映典型样本；两者都不是未来运行的确定保证。
测内存时还要明确是浅层对象大小、峰值Python分配还是进程常驻内存。sys.getsizeof 不会递归统计容器引用的全部对象；tracemalloc 观察Python分配也不等同于整个进程。复制输入、打印日志、磁盘读取与垃圾回收是否计入，要按实际问题决定。
流式随机抽样
不知道流总长度却要等概率保留K项，可以使用蓄水池抽样。先填入K项，处理第i项时，在 0..i-1 中均匀取一个位置；落在前K个位置才替换。新项入选概率为 K/i；旧项本来入选概率为 K/(i-1)，这一轮存活概率为 (i-1)/i，乘积仍为 K/i，因此归纳成立。
代码只保留O(K)条记录，扫描O(n)次。输入可以是一次性生成器。固定种子有助于在同一执行环境复现，但抽样均匀性的证明来自概率推导，不能只靠一次频数统计。random 不用于生成密码或认证令牌；那是另一种随机性需求。
精确解、近似与启发式
NP描述可在多项式时间验证证书的一类判定问题，不能把它展开为“非多项式”。NP困难表示至少和NP问题一样难，不要求问题本身属于NP；P是否等于NP尚未解决。容量DP的伪多项式成本也不能直接解决这个问题。
不易精确求解时，需要明确替代目标。无向简单图的顶点覆盖，可以反复取一条尚未覆盖的边，把两端都加入答案并移除所有关联边。取到的边互不共享端点，任何覆盖至少要为每条这样的边选一个端点；算法选了每条边的两个端点，因此覆盖大小至多最优的两倍。示例的 vertex_cover_2approx 使用这个规则，拒绝自环以保持当前证明前提。
这种近似比有明确保证；随意的启发式可能很有用，却不能省略最坏情况说明。最大流则属于另一类可精确求解的图优化：残量网络允许撤销并重新分配已有流，找不到增广路径时由最小割给出最优性依据。先识别问题模型，再决定是否需要近似或指数搜索。
练习与面试自查
把集合构建纳入计时，分别测试一次查询和多次查询。给抽样加入空流、K=0、K大于流长度测试；对很短的流枚举所有随机分支，检查每项出现次数相同。为顶点覆盖枚举小图的所有顶点子集，验证覆盖性与两倍界。
面试时解释：为什么随机种子不能代替正确性证明；为什么统计上的“通常更快”不同于近似比；为什么在调优前必须先确认两个实现返回同一种结果。
本地运行
示例仅使用 Python 标准库，适用于 Python 3.10 及以上。把 example.py 与 test_example.py 保存到同一个目录，在该目录运行：
python example.py
python -m unittest -v test_example.py
测试检查本文列出的边界；新增练习仍需自己补充断言。