大 O 表示法详解（附示例）

大 O 表示法解决什么问题

用秒数给程序计时，反映的只是某一台机器、某一种语言和某一组输入的情况。大 O 回答的是一个更有用的问题：输入变成 10 倍时，算法的工作量会增加多少？工作量增加 10 倍的算法，与增加 100 倍的算法，伸缩性截然不同。

形式化的定义是：如果存在常数 c 和 n₀，使得对所有 n ≥ n₀ 都有 f(n) ≤ c · g(n)，则称 f(n) 是 O(g(n))。通俗地说，当 n 足够大时，g 是 f 增长速度的上界，且忽略常数因子。

• n 表示输入规模：列表的长度、字符串的字符数、图中的节点数。
• 时间复杂度统计基本步骤的数量（比较、赋值、算术运算）。
• 空间复杂度统计额外使用的内存，不包括输入本身。

如何化简表达式

先把步数写成关于 n 的函数，再应用两条规则：舍去常数系数，只保留主导项。

当算法有两个独立的输入时，两者都要保留：先遍历长度为 n 的列表，再遍历长度为 m 的列表，复杂度是 O(n + m)；循环嵌套循环则是 O(n · m)。对数的底数在大 O 中无关紧要，因为 log₂ n 与 log₁₀ n 只相差一个常数因子。

常见的复杂度类别

粗略的经验：在现代计算机上，Python 的简单循环每秒可执行数千万次基本操作，编译型语言则快得多。因此 O(n log n) 处理上百万条数据没有问题，O(n²) 在数万条左右就会变慢，而 O(2ⁿ) 超过 40 到 60 个元素就基本无法运行。

从 Python 代码读出复杂度

看循环。对输入的单层循环是 O(n)；在同一输入上嵌套的两层循环是 O(n²)；每次把剩余范围减半的循环是 O(log n)。

def first(items):            # O(1): one step, whatever the size
    return items[0]
def total(items):            # O(n): touches each item once
    s = 0
    for x in items:
        s += x
    return s
def has_duplicate(items):    # O(n^2): compares every pair
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False
def halvings(n):             # O(log n): n is halved each step
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps
print(first([7, 8]), total([1, 2, 3]), has_duplicate([1, 2, 1]), halvings(1024))
# 7 6 True 10

库函数调用也有自己的开销。x in some_list 是 O(n)，x in some_set 平均为 O(1)，list.insert(0, x) 是 O(n)，因为每个元素都要后移，sorted() 是 O(n log n)。如果循环里调用了 n 次 O(n) 的操作，即使看起来只有一层循环，整体也是 O(n²)。

def has_duplicate_fast(items):   # O(n) time, O(n) extra space
    seen = set()
    for x in items:
        if x in seen:            # average O(1) set lookup
            return True
        seen.add(x)
    return False
print(has_duplicate_fast([3, 1, 4, 1, 5]))   # True
print(has_duplicate_fast(list(range(10))))   # False

最好、平均和最坏情况

同一个算法在相同规模的不同输入上，工作量可能不同，所以复杂度通常按三种情况来说明。

人们只说「X 的复杂度」时，通常指最坏情况；对哈希表和快速排序则往往指平均情况。均摊代价是第四个概念：向 Python 列表追加元素时，列表扩容的那一次是 O(n)，但在多次追加中平均下来是 O(1)。

大 O、大 Ω 与大 Θ

严格来说，O(n) 的算法同时也是 O(n²)，因为 O 只是上界。日常使用中，人们写的是大 O，想表达的却是自己所知的最紧的界，也就是 Θ 所表示的含义。

常见误区

• 忽略内置操作的开销，例如对列表使用 in，或切片 items[1:]（它会复制 k 个元素，开销为 O(k)）。
• 递归调用次数算错：一个函数对 n − 1 调用自身两次，复杂度是 O(2ⁿ)，而不是 O(n)。
• 忽略空间：新建大小为 n 的列表，或者递归深度达到 n，都要占用 O(n) 内存。
• 写成 O(2n) 或 O(n + 5)。两者都应化简为 O(n)。