Big O 入门：比「跑了几秒」更有用的算法直觉

同一个程序，在不同机器上可能跑出不同耗时。复杂度关心另一个问题：当输入规模增长时，工作量会怎样增长？

先数增长最快的部分

假设处理 n 个元素需要执行 3n + 10 次基础操作。当 n 足够大时，一次性的 10 和系数 3 不会改变线性增长的趋势，我们通常用 O(n) 来表达它的渐近上界。

严格地说，Big O 描述上界，而不是「精确耗时」或「必然的最坏情况」。常见讨论会另外约定分析的是最坏、平均还是摊还复杂度。

两个循环不一定是平方级

# 两次独立遍历：n + n，仍然是 O(n)
for item in items:
    inspect(item)
for item in items:
    save(item)

# 两层遍历：n × n，通常是 O(n²)
for left in items:
    for right in items:
        compare(left, right)

这里假设 inspect、save、compare 都是常数代价。真实程序里，函数内部还可能包含查询、排序或网络调用，不能只数表面上的循环层数。

二分查找为什么是对数级

每次把候选区间减半，从 n 个元素缩小到 1 个，大约需要 log₂(n) 次。1024 个候选项，约 10 次缩小就够了。

但前提是数据有序，并且能高效访问区间中点。如果先为每次查询都重新排序，排序成本也必须计入总成本。

时间之外，还有空间

用哈希集合记录见过的元素，通常可以把重复检查从嵌套比较改成单次遍历。代价是引入额外内存。

def has_duplicate(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

在元素可哈希、哈希操作平均代价可视为常数等假设下，这个方法的平均时间复杂度是 O(n)，额外空间是 O(n)。分析时写出假设，比只背一个结论更有用。

让推断接受测量

分别测量规模为 n、2n、4n 的输入。若耗时大约变成 1、2、4，可以先猜测线性趋势；若接近 1、4、16，则可能有平方级增长。

实验会受到缓存、预热、I/O 与输入分布影响。复杂度帮你选方向，基准测试帮你确认现实。小数据下，常数更小的实现依然可能胜出。