按时完成的算法：复杂度速查

你写了一个函数，在测试数据上运行，它工作正常。然后它进入生产环境——500,000 行而不是 500 行——请求超时了。这种事经常发生，几乎总是因为代码在小规模时看起来合理，但隐藏的复杂度问题。

为什么你的笔记本欺骗了你

O(n²) 算法在 100 个项目上执行 10,000 次操作。这在任何机器上都是瞬间的。在 100,000 个项目上运行相同算法，你得到 100 亿次操作——分钟或小时而不是毫秒。从 n 到 n² 的跳跃看起来不危险，直到 n 变大，这正是为什么它通过了代码审查和本地测试。

一个经典例子：用嵌套循环检查重复项。

def has_duplicates(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

这是 O(n²)。改用集合：

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

现在是 O(n)。集合查找平均 O(1)，所以整个函数线性扩展而不是平方扩展。在 10,000 个项目上，这是大约 1 亿次比较和 10,000 次的区别。

优化前先测量

不要猜测。用 timeit 做微基准：

import timeit
timeit.timeit(lambda: has_duplicates(list(range(5000))), number=10)

对于更大的函数，用 cProfile 分析：

python -m cProfile -s cumulative myscript.py

查看 cumtime 列。如果一个函数消耗了 90% 的运行时间，那就是你的目标。优化不是瓶颈的代码浪费你的时间，并且没有收益地增加了复杂性。

悄悄变慢的常见模式

重复的列表成员检查。 if x in my_list 对列表是 O(n)，但对集合或字典平均是 O(1)。如果你在循环内检查成员，那个 O(n) 检查在 O(n) 循环内给你 O(n²) 的总体。把列表换成集合，你回到 O(n)。

循环中的字符串连接。 在 Python 中，result += chunk 在循环中对字符串是最坏情况 O(n²)，因为字符串是不可变的，每次连接都复制整个东西。使用 ''.join(chunks) 代替——它一次构建字符串。

排序当你不需要时。 sorted() 是 O(n log n)。如果你在循环内调用它只是为了找到每次迭代的最大值或最小值，用 max()/min()（O(n)），或更好的是，如果你需要重复运行极值，用堆（heapq）。heapq.nlargest(k, data) 是 O(n log k)，当 k 很小时比排序整个列表便宜得多。

没有记忆化的递归函数。 朴素递归斐波那契是 O(2ⁿ)，因为它一次次重复计算相同的子问题。加上 functools.lru_cache，它下降到 O(n)：

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

快速从真实代码读出 Big O

计算相同输入上的嵌套循环——那通常是你的指数。单个循环是 O(n)。循环内循环是 O(n²)，除非内循环的范围缩小（像在冒泡排序的优化形式中，仍然最坏情况 O(n²) 但比较更少）。递归调用分割问题为一半的，像二分查找或归并排序，指向 O(log n) 或 O(n log n)。每级分支成多个调用的递归调用，像朴素斐波那契，指向指数时间——强信号表示你需要记忆化或迭代重写。

好习惯：在你在面向用户的数据上写嵌套循环或递归前，问 n 在生产中实际上可能是多少，不是在你的测试文件中。如果 n 可能达到六位数，O(n²) 解决方案在上线前需要再看一眼。

更多关于复杂度分析、排序算法和分析工具，查看 Korra Studio 上的 Python 和计算机科学部分。