时间复杂度和空间复杂度：判断代码随数据增长的代价

问题与目标

一次运行很快，不能证明数据扩大后仍然可用。复杂度忽略机器差异和常数细节，观察基本操作与输入规模之间的增长趋势。

完成标准：能判断常见循环、二分和哈希查找的复杂度，区分最坏情况与平均情况，并通过实验验证增长趋势。本篇不进行渐近符号的严格证明。

这张图比较的是增长速度，不是某台机器上的精确运行时间。输入规模较小时差异并不显眼，规模扩大后，线性、线性对数和平方级算法之间的代价才会迅速拉开。

核心概念

大 O 通常描述增长上界。分析时保留增长最快的项并忽略常数，例如 3n² + 5n + 2 记作 O(n²)。常见顺序为：

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

嵌套循环不一定就是 O(n²)，要看每层执行次数；连续步骤通常相加，最终保留最高阶。哈希表查询平均可视为 O(1)，但不能把平均情况说成无条件保证。

空间复杂度关注额外内存随输入增长的趋势。原地修改可能是 O(1) 额外空间，复制列表通常是 O(n)；递归调用栈也计入空间。

常见代码结构怎样分析

def examples(values: list[int]) -> None:
    print(values[0])                    # O(1)
    for value in values:               # O(n)
        print(value)
    for left in values:                # O(n²)
        for right in values:
            _ = left == right

连续的 O(1) + O(n) + O(n²) 最终记作 O(n²)。若循环每轮让问题规模减半，例如二分查找，循环次数约为 log₂n。递归复杂度需要同时分析每层工作量和递归层数。

内置操作也有成本：

“平均”与“均摊”含义不同：哈希查询的平均复杂度依赖哈希分布；动态数组追加的均摊复杂度表示少数扩容成本分摊到多次追加。

可运行实现

比较列表扫描与集合查找。计时受机器和运行状态影响，观察数据规模翻倍后的趋势：

from time import perf_counter


def contains_list(values: list[int], target: int) -> bool:
    return target in values


def contains_set(values: set[int], target: int) -> bool:
    return target in values


def measure(size: int) -> None:
    values_list = list(range(size))
    values_set = set(values_list)
    target = -1

    started = perf_counter()
    for _ in range(100):
        contains_list(values_list, target)
    list_time = perf_counter() - started

    started = perf_counter()
    for _ in range(100):
        contains_set(values_set, target)
    set_time = perf_counter() - started

    print(size, round(list_time, 6), round(set_time, 6))


for current_size in (10_000, 20_000, 40_000):
    measure(current_size)

列表未命中需要扫描全部元素，时间大致随 n 增长；集合查找平均增长较慢，但集合本身需要额外 O(n) 空间和构建时间。只查询一次时，先建集合未必划算；大量重复查询时收益更明显。

输入是三种规模的整数集合和一个不存在的目标，输出是两种查询方式各执行 100 次的耗时。结果不要求具体秒数一致，而是观察列表耗时随规模近似增长、集合查询变化较小。

时间与空间的取舍

判断重复元素可以双重循环，只用常数额外空间但需要 O(n²) 时间；也可以使用集合，在 O(n) 平均时间内完成，但需要 O(n) 额外空间。不存在脱离约束的“最优算法”。

性能实验建议记录：输入生成方式、数据规模、重复次数、Python 版本和机器环境。使用 timeit.repeat() 取多次结果，比只测一次更可靠；需要定位函数内部热点时再使用性能分析器。

进一步验证

1. 分析“先把列表转为集合，再查询 q 次”的总成本，说明 q 很小时为何未必划算。
2. 将输入规模扩大 2 倍和 4 倍，重复测量并保存一张结果表。
3. 为测量结论附上环境、重复次数和输入特征，不只报告一个秒数。

最终应能分开渐近复杂度与实测耗时，并说明结论适用的工作负载。

常见问题与排查

• 把大 O 当成秒数：它描述增长趋势，不给出具体耗时。
• 忽略内置操作成本：x in list 是线性扫描，list.insert(0, x) 要移动元素。
• 看到双层循环就写 O(n²)：若内层总共只推进 n 次，整体可能仍是 O(n)。
• 只分析时间：更快的方法可能用更多内存，需结合约束取舍。
• 用一次微秒级测试下结论：增加规模和重复次数，并使用 timeit 或性能分析器。

小结

复杂度提供的是容量判断，不是性能承诺。正确方法是先做渐近分析，再在真实数据规模和环境中测量，最后结合时间、空间和代码清晰度选择实现。