Algorithm

复杂度分析

学习用大 O 表示法分析算法的运行时间和内存如何随输入规模增长，并通过实际测量来验证分析结果。

复杂度分析描述的是：当输入变大时，算法所需的时间和内存会增长多少。它不用依赖硬件和语言的秒数，而是把基本操作次数写成输入规模 n 的函数，只保留最高阶的项。结果用渐近记号表示：大 O 表示上界，大 Ω 表示下界，大 Θ 表示紧确界。

数据量一大，不同增长阶之间的差距就会超过任何常数因子，这正是复杂度分析重要的原因。处理一千个元素没问题的 O(n²) 代码，面对一百万个元素可能要跑上几个小时，而 O(n log n) 的代码几秒钟就能完成。选择数据结构、解读编程题的输入范围、在代码评审中发现隐藏开销、估计系统能否扩展，都离不开复杂度分析。

先从数清简单循环的操作次数开始，熟悉常见的复杂度类别：O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 和 O(n!)。然后再学习最好、平均和最坏情况，均摊分析，空间复杂度，以及用主定理求解递推式。学习过程中要养成用倍增实验检验分析的习惯：分别在 n 和 2n 下计时，再比较两者的比值。

特点

渐近记号

O、Ω 和 Θ 忽略常数因子和低阶项，分别给出增长速度的上界、下界和紧确界。

计算操作次数

顺序执行的代码把开销相加，嵌套循环把开销相乘，每一步把问题规模减半就会得到对数。

均摊分析

把一系列操作的总开销平均到每次操作上。这就是动态数组追加元素偶尔要整体复制，却仍是 O(1) 的原因。

空间与递归

辅助内存和递归深度同样计入开销，分治算法的递推式可以用主定理求解。

适用场景

在算法面试和编程竞赛中根据输入范围选择解法
选择哈希表、堆、平衡树等数据结构
在代码评审中找出隐藏的嵌套循环
预估系统扩展能力并优化性能瓶颈

参考实现

用 O(n²) 和 O(n) 解两数之和

脚本用两种方法解决同一个问题：检查所有数对，或者只遍历一次并用字典记住已经见过的值。用 timeit 在 n = 500、1,000、2,000 时分别计时，可以看到 n 每翻一倍，平方版本大约慢 4 倍，线性版本大约慢 2 倍。

complexity.py

import timeit


def two_sum_quadratic(nums, target):
    """O(n^2): try every pair."""
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return i, j
    return None


def two_sum_linear(nums, target):
    """O(n) on average: remember values already seen."""
    seen = {}
    for j, x in enumerate(nums):
        i = seen.get(target - x)
        if i is not None:
            return i, j
        seen.setdefault(x, j)
    return None


print(two_sum_quadratic([8, 3, 11, 5, 2], 13), two_sum_linear([8, 3, 11, 5, 2], 13))

for n in (500, 1_000, 2_000):
    nums = list(range(0, 2 * n, 2))  # even numbers only, so no pair sums to -1
    slow = timeit.timeit(lambda: two_sum_quadratic(nums, -1), number=3) / 3
    fast = timeit.timeit(lambda: two_sum_linear(nums, -1), number=3) / 3
    print(f"n={n:>5}  O(n^2) {slow * 1000:8.2f} ms   O(n) {fast * 1000:6.3f} ms")

python complexity.py

分步指南

共六章，带你从安装一步步了解复杂度分析的核心概念。

官方文档与参考资料

讨论

发起讨论

在这里提问、分享经验，交流关于复杂度分析的看法。

还没有讨论。来发起第一个吧。