Hello 算法 2.1 精讲：怎样评估算法效率，才不会被一次跑分快慢误导

先建立主线：正确、可用，再比较资源成本

算法效率评估，就是在任务和约束相同的前提下，考察解决问题需要多少时间与空间。实际测试回答“这个实现，在这组输入和这台机器上表现怎样”；复杂度分析回答“在明确的计算模型下，输入规模增长时，工作量和所需状态怎样增长”。两者共同支持选择。

原书 2.1 包含时间与空间两个维度、实际测试和理论估算两种方法。本文围绕这条主线重新讲解；重复检测、Python 实验、边界和复盘题为原创补充，不是原书逐段翻译。下面先不用背 O 符号，先数清楚工作和保留的状态。

知识点 01：先证明在解决同一个问题

假设你要检查一次测试执行列表里是否出现重复编号。把问题简化为：输入一个有限的普通整数列表，存在任意两个不同位置的相同整数就返回 True，否则返回 False；不能修改输入。没有并发修改，也不讨论自定义比较方法。

只检查相邻项的程序，在 [4, 7, 4] 上会给错答案；它即使更快，也不满足本任务。若另一方案先排序并改写输入，必须计入复制或明确允许修改，才能与“不修改输入”的方案公平比较。正确性与接口约束是比较的前提。

知识点 02—03：时间与空间分别在衡量什么

“更快”和“更省”可能冲突：记下已经出现的值，可以减少重复查找，却需要额外存储。若系统有严格内存上限，耗时稍少但超出内存预算的方案仍不可用。

时间还分经过时间与 CPU 时间。经过时间包含等待、调度等；CPU 时间反映进程使用的 CPU 时间。等待设备恢复时，用户关心经过多久；比较纯计算片段时，要注明计时器口径。空间也不能只看函数返回后的剩余内存：中途创建的大对象可能已释放，真正危险的是过程中的峰值。

知识点 04—05：实测与理论估算是怎样配合的

原书强调实测会受硬件和输入规模影响。工程中不必穷举所有机器才可得到有用结论：可以限定目标部署环境，选择代表性输入进行测试；结论的适用范围随证据写清楚。

理论分析抽掉部分实现细节，便于看增长规律；它仍依赖模型。例如把整数比较视为固定成本是一项前提。超长整数、昂贵的自定义比较、磁盘 I/O 或并行执行都可能要求扩展模型。抽象分析有适用条件，实测有实验边界。

知识点 06：先读懂两个满足相同规格的实现

方案 A：枚举每一对不同位置。left 从 0 向右移动；right 从 left + 1 开始，所以不会与自身比较，也不会把同一对反过来重复比较。发现相等就立即返回 True，所有候选对都不相等才返回 False。

方案 B：准备一个集合 seen，记录已经检查过的值。先检查当前值是否已在集合中；若在，说明此前位置已经出现过；若不在，把它记入集合，继续下一项。检查必须在加入之前。否则当前值会与刚加入的自己匹配。

下面两个函数以及后续实验都以本节整数列表为前提，并未实现通用输入校验。若改成列表元素也是列表，集合方案会因元素不可哈希而抛出 TypeError；不能把整数实验直接推广到任意对象。

下面五行的两个布尔结果应分别为 False/False、False/False、False/False、True/True、True/True。

语义依据：Python 集合类型。

def has_duplicate_pairs(values):
    for left in range(len(values)):
        for right in range(left + 1, len(values)):
            if values[left] == values[right]:
                return True
    return False

def has_duplicate_seen(values):
    seen = set()
    for value in values:
        if value in seen:
            return True
        seen.add(value)
    return False

for values in ([], [4], [4, 7], [4, 7, 4], [-1, 0, -1]):
    print(values, has_duplicate_pairs(values), has_duplicate_seen(values))

知识点 07：用 [4, 7, 4] 手工追踪状态

表中集合的书写顺序只为阅读方便，不表示集合承诺按这个顺序遍历。方案 B 每轮开始时，seen 恰好包含此前位置的值：成员检查为真便能证明出现重复；为假时加入当前值，维持这条性质。有限列表每轮推进一个位置，或者提前返回，所以会终止。

注意方案 A 在此只比较两次，不能据此说它对长度 n 的任意输入都只比较两次。一次执行轨迹，与所有合法输入上的成本分析，是两层不同的证据。

知识点 08—09：先数操作，再谈增长

用所有元素都不同的输入观察：方案 A 不会提前返回。left=0 时比较 n−1 次；left=1 时比较 n−2 次；一直到最后不需要再比较。总比较次数是 (n−1)+(n−2)+…+1 = n(n−1)/2，n 为 0 或 1 时次数为 0。

方案 B 会遍历 n 项，每项进行一次成员检查和一次加入。这里的 n 是成员检查次数，不是集合底层所有操作的总数；比较次数与集合操作次数也不是相同成本的单位。

固定大小整数操作视为常数成本时，方案 A 在无重复输入上的时间增长为 Θ(n²)；普通哈希分布下，方案 B 的期望总时间增长为 Θ(n)。集合的哈希冲突可能增加成本，不能把每次成员查找都无条件当作最坏 O(1)。本节实测的连续小整数数据不能验证所有碰撞情况。

下面的小程序只统计索引对数量，不执行重复检测；输出列依次是 n、索引对数、成员检查次数。不要把加上计数器后的程序拿去代表原程序的真实耗时。

def pair_count(n):
    comparisons = 0
    for left in range(n):
        for right in range(left + 1, n):
            comparisons += 1
    return comparisons

for n in (0, 1, 2, 4, 8):
    print(n, pair_count(n), n)

知识点 10：输入规模相同，工作也可能不同

长度相同，不等于执行路径相同。用 n=6 比较：输入 [4, 4, 0, 1, 2, 3] 时，方案 A 第一次比较就返回；输入 [0, 1, 2, 3, 4, 5] 时，它必须比较 15 对。方案 B 也分别在第 2 项和第 6 项结束。

随机生成值的范围太小，长列表很早就出现重复，可能完全观察不到无重复路径的平方增长。平均情况也需要指定输入分布；对固定输入反复计时七次，得到的是这组输入上的测量分布，并不自动得到算法的平均情况复杂度。

知识点 11：增长慢的算法，为什么小数据时也可能更慢

为了单独看清机制，假设两种方案的成本模型为 A(n)=2000+20n、B(n)=2n²。它们是人为设定的成本单位，不是前面两个 Python 函数的计时结果，也不是拟合数据。A 的固定准备成本更大，但增长更慢。

复杂度主要描述规模增大时的增长阶，不保留这里的全部常数和准备成本。所以“更低的渐近增长”与“我当前的小输入更快”可以同时不一致。实际交叉位置要根据具体实现分析或测量，不能直接从这个虚构模型迁移过去。

for n in (10, 100, 1000):
    cost_a = 2000 + 20 * n
    cost_b = 2 * n * n
    print(n, cost_a, cost_b)

知识点 12：计时器包住哪里，你就测了什么

如果计时范围包含生成输入、算法和 print，得到的是这三个阶段及其他开销的总时间。它也许符合端到端需求，但不能直接归因到算法本身。若只想比较计算函数，应把相同数据准备放在计时外，并把输出也移出去。

Python 的 perf_counter() 适合测量短时间段；两个读数相减得到经过秒数，起点不是日历时间，不应当作时间戳存储。它包含睡眠和等待。timeit 默认使用这个计时器，并通过重复执行减少单次微小耗时的计时占比。

若要测试“建一次索引，查询一千次”，那就是另一种任务边界，应把建索引和全部查询放到相应范围。排序会修改输入、生成器会被耗尽、有缓存的函数会改变后续调用路径；这些场景需要重建输入或分开报告冷启动和预热结果。

依据：Python · perf_counter、timeit。以上实验设计是本文补充。

知识点 13：一份可复现的多轮计时实验

下面是完整脚本，可保存为 performance_evaluation.py 后用 python3 执行。两种方案使用相同无重复列表；每种先预热三次，再采集七轮，每轮完整调用二十次。轮与轮之间交换先后顺序，缓解固定顺序带来的影响，但并未消除所有系统干扰。

Timer.timeit(number=20) 返回二十次调用的合计秒数；除以 20，再乘 1,000,000，得到这一轮的平均微秒/次。七轮产生七个这样的样本，代码保留原始样本并输出最小值、中位数和最大值。这不是单次请求延迟的七个样本，也不是 p95 或置信区间。

timeit 文档建议在典型微基准中把最小值视为较少受其他进程干扰的下界估计；这里额外保留中位数、最大值和原始轮次，便于观察噪声。这个下界仍包含包装开销，并不是跨机器性能保证。默认 timeit 会在计时阶段暂时禁用循环垃圾回收；若任务依赖 GC，需要改实验并记录，而不能把本实验当作线上端到端结果。

import json
import platform
from statistics import median
from timeit import Timer

def has_duplicate_pairs(values):
    for left in range(len(values)):
        for right in range(left + 1, len(values)):
            if values[left] == values[right]:
                return True
    return False

def has_duplicate_seen(values):
    seen = set()
    for value in values:
        if value in seen:
            return True
        seen.add(value)
    return False

print(json.dumps({"python": platform.python_version(),
                  "implementation": platform.python_implementation(),
                  "system": platform.system(),
                  "machine": platform.machine()}, sort_keys=True))
functions = [("pairs", has_duplicate_pairs), ("seen", has_duplicate_seen)]
number = 20
for n in (64, 256, 1024):
    values = list(range(n))  # 数据构造在计时外；每个元素不同
    samples = {name: [] for name, _ in functions}
    for _, function in functions:
        assert function(values) is False
        for _ in range(3):
            function(values)  # 预热，不计入样本
    for round_index in range(7):
        order = functions if round_index % 2 == 0 else functions[::-1]
        for name, function in order:
            timer = Timer(lambda: function(values))
            elapsed_s = timer.timeit(number=number)
            samples[name].append(elapsed_s / number * 1_000_000)
    for name, _ in functions:
        times = samples[name]
        print(json.dumps({"n": n, "algorithm": name, "rounds": len(times),
                          "calls_per_round": number, "samples_us": times,
                          "min_us": min(times), "median_us": median(times),
                          "max_us": max(times)}, sort_keys=True))

实验记录：只解释这组已运行的数据

2026-10-15 实际运行完整脚本，环境：CPython / 3.12.14 / Linux / x86_64。输入为无重复的 list(range(n))；每项七轮，每轮二十次。单位：微秒/次，每个样本为一个批次内的平均值。

本次共享运行环境存在明显波动，例如 n=64 的集合方案最小值与最大值差距较大。因此不据此宣布精确加速比例或跨环境排名。这组无重复输入上，集合方案的七轮批次平均值均低于两两比较；选择实现还需要实际数据分布与内存预算。

测量并不证明复杂度；候选对数量的推导解释增长。只有三个规模，也未单独控制 CPU 频率或运行多个独立进程，不能把这组观察解释为所有 Python 实现上的性能规律。

知识点 14—15：看峰值，也要说清楚测量范围

方案 A 只保留索引等少量工作状态；方案 B 的集合可能保留 n 个不同整数的引用和哈希表结构，辅助空间会随 n 线性增长。在固定大小数值/机器字的常用模型下，二者分别为 O(1) 与 O(n) 辅助空间；若按任意长整数和索引的精确位数计算，需要进一步展开，不能把“常数个变量”解释成任意输入下固定字节数。

下面完整脚本用 tracemalloc 测量追踪范围内的 Python 内存块，输入在追踪前创建，两种方案分别重新开始追踪。get_traced_memory() 返回 current（此刻仍在追踪的字节）和 peak（这一追踪区间达到过的最高值）。函数返回时内部集合已不再需要，current 可能很小；peak 仍留下中间占用的信息。

这里测到的峰值既不是整个进程的 RSS，也不覆盖所有原生库或设备内存。已存在的输入整数不在本轮新分配追踪里；集合本身的分配在范围内。工具也会带来开销，因此内存实验与计时实验分开运行。若要测进程总内存，必须换相应指标并保留基线。

另一个常见误区是只用 sys.getsizeof(values) 代表列表及全部元素：官方文档明确它只统计直接归属于该对象的内存，不递归累计被引用对象。共享对象还要避免重复计数。

依据：tracemalloc · 当前值与峰值、sys.getsizeof · 直接对象大小。

RSS（Resident Set Size，常驻内存大小）描述进程当前驻留物理内存的范围，还受解释器、分配器和其他模块影响；它与本脚本的 Python 分配追踪口径不同。O(1) 辅助空间也没有说“内存为零”，而是在选定模型下不随 n 线性增加。

两种方案在本次函数返回后追踪存活量均为 0，但峰值明显不同。这是本环境该输入上的读数，不能当作其他机器或任意 n 的固定字节公式。

import gc
import json
import tracemalloc

def has_duplicate_pairs(values):
    for left in range(len(values)):
        for right in range(left + 1, len(values)):
            if values[left] == values[right]:
                return True
    return False

def has_duplicate_seen(values):
    seen = set()
    for value in values:
        if value in seen:
            return True
        seen.add(value)
    return False

values = list(range(1024))  # 输入在追踪前创建，本实验排除输入构造
for name, function in (("pairs", has_duplicate_pairs), ("seen", has_duplicate_seen)):
    gc.collect()
    tracemalloc.start()  # 作为独立脚本运行；每种方案重新开始追踪
    result = function(values)
    current_bytes, peak_bytes = tracemalloc.get_traced_memory()
    tracemalloc.stop()
    print(json.dumps({"algorithm": name, "result": result,
                      "current_bytes": current_bytes,
                      "peak_bytes": peak_bytes}, sort_keys=True))

知识点 16：几种结论为什么证据不足

工程决策还要看负载频率、可维护性、内存预算和正确性风险。本节的七轮是便于运行的教学实验，并非通用统计充分性标准；高成本决策需更多独立进程、代表性数据和更严格的实验控制。

本节复盘：先自己回答，再展开参考答案

1. 为什么“只比较相邻元素”不能直接参加本节的性能比较？
2. 方案 A 在 [0, 1, 2, 3] 上依次检查哪些索引对？比较几次？
3. 在 seen.add(value) 之后再判断 value in seen，会发生什么？
4. 二十次调用总耗时 0.004 秒，平均一次多少微秒？七轮中位数代表单次请求的 p50 吗？
5. n 从 1000 增加到 2000，无重复路径上的候选对数是否恰好四倍？
6. 两种函数返回后的 current 接近，为什么仍可能有很大的 peak 差异？
7. 测试记录很短、重复常在开头，是否能只凭无重复大列表计时选择实现？
8. 集合方案能直接用于 [[1], [1]] 吗？这提示了什么比较前提？

建议练习：把计时输入改成开头重复与很晚重复的两组数据；先手工预测路径，再保留相同计时范围进行比较。上述题目与实验属于作者建议，不记作你已提出、完成或掌握。

来源、验证范围与下一步

主题依据：krahets / 《Hello 算法》2.1 算法效率评估，2026-10-15 核对。本文重新组织内容，加入原创重复检测、执行状态、成本推导、测量脚本、误区与复盘题。相关改编文字采用 CC BY-NC-SA 4.0，保留署名、来源和改动说明，遵守非商业及相同方式共享；不改变本站其他内容或源码许可。

Python 机制核对官方 timeit、time、tracemalloc 和 sys.getsizeof 文档。集合底层成本属于实现与模型前提，详见 本次验证版本的 CPython 集合源码；本节不把哈希期望分析当作 Python 语言的最坏性能保证。

本节只覆盖 2.1；下一篇可读已发布的 2.2 迭代与递归。下一轮计划细讲 2.3 时间复杂度，推导增长阶、渐近符号与输入情况；它当前仍是待编写条目，以覆盖表为准。

验证环境 CPython 3.12.14：执行五段代码，其中三段核对精确标准输出，另两段验证计时/内存记录结构与统计一致性；1,098 组输入逐一核对两个函数与独立计数答案（2,196 个结果），并检查输入未修改。另核对 n=0…65 的 66 个操作计数、超长整数示例及不可哈希输入的异常。性能读数只作本次观察，没有设置“必须快多少”的测试门槛。