算法分析基础：两段代码差在哪

12 min入门2026/10/11

以「同算 1 加到 100，一个瞬间一个卡三秒」引入，用真实计时实验建立大 O 直觉：时间与空间两本账、五级复杂度阶梯、最好/最坏/平均与 Ω/Θ 记号、给代码判复杂度的读法，本模块以 Python 为教学语言。

前置知识

会写 Python 的循环与函数（控制流级别即可）。本模块所有示例用 Python，让你在每个算法上都能立刻跑。

学习目标

读完本文你将能够：

用「增长趋势」而不是「秒数」评价一段代码的性能；
说出七级常见复杂度 O(1)/O(log n)/O(n)/O(n log n)/O(n²)/O(2ⁿ)/O(n!) 各自的增长画像与生活对照；
给一段简单代码同时算清两本账——时间复杂度与空间复杂度，并理解递归为什么可能「崩」而不只是「慢」；
区分最好、最坏、平均三种口径，知道 Ω、Θ 与 O 各自在说什么，以及工程上为什么盯最坏情况；
给一段简单代码标出大 O，并用 timeit 实验验证自己的判断。

预计 60 到 90 分钟，含三组计时实验与一组动手自检。

1. 你现在要解决什么问题

同样「1 加到 100」：一个人从 1 加到 100 加了一百次，另一个人用高斯配对法 (1+100) × 50 一次算完。结果相同，代价天差地别。n=100 时你感觉不出来，n=1000 万时一个方案跑一晚、一个跑一瞬——写代码的人必须能在写下的那一刻就知道自己选的是哪种代价。大 O 记号就是这套「代价语言」。

2. 最小可运行实验：亲手计时

把两种加法写出来，用 timeit 计时（标准库自带，无需安装）：

python

import timeit

def sum_loop(n):
    total = 0
    for i in range(1, n + 1):
        total = total + i
    return total

def sum_formula(n):
    return n * (n + 1) // 2

for n in (1000, 100000, 10000000):
    t1 = timeit.timeit(lambda: sum_loop(n), number=1)
    t2 = timeit.timeit(lambda: sum_formula(n), number=1)
    print(f"n={n:>9}  循环版 {t1:.4f}s  公式版 {t2:.6f}s")

预期输出（数字因机器而异，趋势一致）：

text

n=     1000  循环版 0.0312s  公式版 0.000001s
n=   100000  循环版 3.1042s  公式版 0.000001s
n= 10000000  循环版 310.99s  公式版 0.000002s

读表：n 扩大 100 倍，循环版耗时也扩大约 100 倍（线性），公式版纹丝不动（常数）。大 O 度量的就是这个「n 扩大时代价怎么涨」的趋势——循环版是 O(n)，公式版是 O(1)。

3. 发生了什么：为什么只谈趋势

大 O 忽略常数与低阶项：3n + 500 记作 O(n)。因为 n 足够大时，常数与低阶项对趋势毫无影响——我们关心的是「n 上亿时它会不会要我的命」。判断口诀三步：

只有常数步、不看输入 → O(1)；
循环次数随 n 翻倍而翻倍 → O(n)；循环套循环（内层也随 n）→ O(n²)；
每轮把问题规模砍半（二分）→ O(log n)；砍半后每层还要线性扫（归并/快排）→ O(n log n)。

4. 核心概念一：七级阶梯与生活对照

复杂度	n=1 千	n=100 万	生活对照
O(1)	瞬间	瞬间	按学号在点名册直接翻页
O(log n)	瞬间	约 20 步	二分查字典（每页砍一半）
O(n)	很快	约 1 秒	一页页翻完整本册
O(n log n)	快	约 20 秒	高效排序的代价
O(n²)	约 1 秒	约 12 天	每人与其余每人握手一次
O(2ⁿ)	约 10³⁰⁰ 步	宇宙热寂也跑不完	细胞分裂：每轮每个都一分为二
O(n!)	不可计算	不可计算	全排列：n 个物品的所有排法

两件事立刻可推：n=100 万时，O(n²) 与 O(n) 差着「天」与「秒」的量级；把 O(n²) 降成 O(n log n) 或 O(n)，是算法工作的核心回报。

后两级补充两个信号：

O(2ⁿ)：每层决策「选 / 不选」两路分叉的穷举（子集枚举）。注意 n=1000 时它不是「慢」，是物理上不可完成——2¹⁰⁰⁰ 远超宇宙原子数；
O(n!)：排列类穷举（旅行商的朴素解）。n ≥ 4 时 n! 已经超过 2ⁿ，是比指数更凶的增长。遇到它们不代表没救：剪枝、动态规划、近似算法都是逃生门，后面的回溯与 DP 篇会反复回到这张表。

5. 核心概念二：空间复杂度——同一份代码的第二本账

时间之外还有一本账：代码运行要额外占多少内存。统计口径三条，与时间复杂度完全对称：

数「暂存数据 + 栈帧空间」，输入本身不计——输入是你拿到的东西，不是你花掉的成本；
只保留最高阶项：一个长度 n 的辅助列表是 O(n)，一个固定大小的计数器是 O(1)；
递归的函数调用栈也是空间：递归深度 n 就有 n 个栈帧同时在内存里，空间 O(n)。

亲手验证「递归的空间账不是慢，是会崩」：

python

import sys, timeit

def sum_recur(n):
    if n == 0:
        return 0
    return n + sum_recur(n - 1)   # 递归深度 n：n 个栈帧同时压在内存里

print(sys.getrecursionlimit())    # 默认 1000：Python 给调用栈设的安全线
try:
    sum_recur(10000)
except RecursionError:
    print("RecursionError: 深度 10000 直接崩，不是慢")

# 深度合规时，递归也比迭代贵：每次调用都有压栈出栈的固定开销
t_iter = timeit.timeit(lambda: sum(range(901)), number=1000)
t_rec  = timeit.timeit(lambda: sum_recur(900), number=1000)
print(f"迭代 x1000: {t_iter:.4f}s   递归 x1000: {t_rec:.4f}s")

实测（数值因机器而异，倍数关系稳定）：

text

1000
RecursionError: 深度 10000 直接崩，不是慢
迭代 x1000: 0.0062s   递归 x1000: 0.0787s

三个读数：

sum_recur(10000) 抛 RecursionError——空间复杂度 O(n) 的递归在 n 超过调用栈深度限制时直接失败。这就是为什么树的深度动辄几十万（如链式存储的大文件）时，DFS 要改显式栈或迭代；
同样算 1 到 900 的和，递归版比迭代版慢一个数量级：每次函数调用都有压栈/出栈/参数传递的固定开销。时间 O(n) 相同，常数差 10 倍；
递归不是不能用——树、图、分治、回溯天然是递归的形状（140 篇展开）。要建立的心智模型是：迭代把状态摊平在堆上（O(1) 栈空间），递归把状态叠在栈上（O(深度) 栈空间），选哪个是时空权衡。

两个常见命名冲突提前排雷：数据结构的「堆」（090 篇）与内存管理里的「堆」（动态分配区域）只是重名，不是同一个东西；「栈」同样如此——调用栈是递归计账的对象，栈数据结构（040 篇）是先入后出的容器。

最后一个工程直觉：空间通常比时间便宜。时间超了请求直接超时，空间超了只是多花钱买内存，所以「以空间换时间」是比反方向更常用的策略——哈希表（070 篇）就是用 O(n) 空间把查找从 O(n) 换到 O(1) 的经典交易。

6. 核心概念三：最好、最坏与平均——O、Ω 与 Θ

「这段代码是 O(n)」其实只说了一半：O 是上界（最坏不差于它），对应的还有下界记号 Ω（最好也不快于它）与紧界 Θ（上下界重合时用它）。同一段代码三种口径可能完全不同，最直观的例子是列表查找：

python

import timeit

arr = list(range(1000000))
print(timeit.timeit(lambda: 0 in arr,          number=100))  # 最好：第 1 个就命中
print(timeit.timeit(lambda: 500000 in arr,     number=100))  # 平均：扫一半
print(timeit.timeit(lambda: 1000007 in arr,    number=100))  # 最坏：扫完才知道没有

实测（数值因机器而异）：

text

0.000s   命中首元素
0.267s   命中中位元素
0.542s   目标不存在（扫完全表）

三种口径的关系一目了然：最好情况 Ω(1)、平均 Θ(n/2)、最坏 O(n)。工程上有两条固定结论：

以最坏情况作为承诺。接口延迟、批处理窗口、SLA 都是「最坏不能超过多少」，没有人敢拿「平均很快」对客户说话；排序算法文档里的复杂度若无特别说明一律指最坏；
平均情况要看输入分布。快排平均 O(n log n)、最坏 O(n²) 的差距，靠随机选主元把「坏输入」变成小概率事件——这层权衡在排序参考篇展开。

务实提示：日常交流里大家都把 O 当 Θ 用（说「快排 O(n log n)」其实是 Θ）。口头沟通无妨，但要知道规范里三者不等价：O 只是「不差于」的上界，O(n²) 的代码你说它 O(n³) 也没错——只是毫无信息量。

7. 调试实录：判复杂度的三个常见误判

误判一：忽略隐藏的循环。sum(arr2d) 看似一行，若是双层列表求和，实际是 O(n²)（行 × 列）。规则：每层「随 n 变化的循环」都相乘。

误判二：把函数调用当免费。循环里调用的函数若自身是 O(n)，整体是 O(n²)——判复杂度要把调用栈里的循环都算进去。修正手段固定：写完代码先数循环层数，再用 timeit 抽查一次趋势。

误判三：把最好情况当日常。x in arr 找首元素是 O(1)，但那取决于输入运气；断言「这行很快」之前先问「最坏输入长什么样」。修正是定式的：先写最坏输入的测试，再谈性能。

8. 修改实验

给 sum_loop 换成 total = total + i 的步长 2 版本（只加奇数）——预测复杂度是否变化（常数减半不改趋势），验证；
把 n 拉到 2000 万，验证 O(n) 的「翻倍即翻倍」预测；
用 timeit 对比 1000000 in arr（列表查找）与 1000000 in s（集合查找，先 s = set(range(1000000))）——体验 O(n) 与 O(1) 的日常差距，这也是「为什么有哈希表」的种子（070 篇）；
把 sum_recur 改成「每层只递归一半」的二分求和（n + sum_half(n//2) 形状想不通就先跳过，170 篇的二分会给完整版），用 n=100000 验证：递归深度变成 O(log n) 后，RecursionError 消失——递归的空间账由深度决定，不由总工作量决定；
用 sys.setrecursionlimit(200) 把调深限制降到 200，再跑 sum_recur(500)，观察崩点随限制移动——确认「崩」的阈值正是栈帧数。

9. 小练习

预测题（先写答案再验证）：下面两段的复杂度各是多少？

python

def a(arr):                 # arr 长 n
    return arr[0] + arr[-1]

def b(arr):
    for x in arr:
        for y in arr:
            if x == y: return True
    return False

追问（时间之外）：a 与 b 各自的空间复杂度是多少？b 的最好情况是什么？

修改题：把 O(n²) 的「找两数之和等于 target」暴力双循环，改用集合降到 O(n)（提示：边遍历边把「需要的另一半」存进集合），并用 n=100000 验证耗时变化；说出这次优化在空间上付出了什么。

修 Bug 题：同事抱怨「列表查重太慢」，代码是 for x in arr: if arr.count(x) > 1——指出复杂度并给出 O(n) 修法。

挑战题（不看提示）：写一段程序实测「O(log n) 的二分查找 vs O(n) 的线性查找」在 100 万有序数组中查找 100 万个不同目标的总耗时，输出对照表，并用本文的阶梯表解释结果。

10. 动手实践：遮代码自检

先只读任务与提示，自己写完再看参考实现。

任务：写 first_dup(arr) 返回第一个重复元素（没有返回 None）。要求：时间 O(n)、空间 O(n)。写完先自己预测它在 10 万元素上的耗时量级，再实测。

提示：遍历过程中需要「O(1) 判断某个值见过没有」——回想第 8 节第 3 条实验里集合查找的实测结果；用一个集合记录见过的元素，判断在前、记录在后。

参考实现（先自己写完再往下看）：

python

def first_dup(arr):
    seen = set()
    for x in arr:
        if x in seen:      # O(1) 查找：集合的哈希表在后面（070 篇）展开
            return x
        seen.add(x)
    return None

# 自检：first_dup([3,1,4,1,5]) 应返回 1；first_dup(list(range(100000))) 应返回 None
# 空间账：seen 最多存 n 个元素 → O(n)，正是换取时间 O(n) 的那笔交易

任务：把 sum_recur 改写成迭代版，时间 O(n)、空间 O(1)，并验证 sum_recur(10000) 崩掉的输入它不再崩。

提示：递归的「递」是把 n 一路减到 0，「归」是逐层加回来；迭代版直接用一个累加变量从 1 数到 n，不需要任何栈。

参考实现（先自己写完再往下看）：

python

def sum_iter(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

print(sum_iter(10000))    # 50005000；没有栈帧堆积，深度不再是问题
# 心智模型回顾：递归把状态叠在调用栈上（O(n) 空间），迭代把状态摊平成一个变量（O(1)）

11. 什么时候应该 / 不应该死磕复杂度

应该：数据量到万级以上、代码要在生产跑、或准备技术面试时——大 O 是通用沟通语言。

不应该：n 永远是个位数的小脚本（可读性优先）；拿大 O 否定一切常数优化（小数据上常数可能主导，实测说话）。

12. 与之前和之后的知识的关系

往前：python 050/060 的循环与函数是本文的实验材料；
往后：数组与动态数组用本文的语言解释「随机访问为什么 O(1)」，并把「均摊分析」引入视野；排序参考篇把 O(n log n) 落到每一种排序；回溯是 O(2ⁿ)/O(n!) 阶梯的正面战场；二分查找是 O(log n) 的完整专题；
更远：面试与工程评审里，大 O 是把「感觉慢」翻译成「可讨论」的通用语言；code review 时先问空间账再问时间账，是资深工程师的习惯。

13. 官方文档

timeit（计时实验的标准工具）：https://docs.python.org/zh-cn/3/library/timeit.html
sys.getrecursionlimit / setrecursionlimit（递归深度限制）：https://docs.python.org/zh-cn/3/library/sys.html#sys.getrecursionlimit
Python 复杂度 wiki（各内置操作的大 O 速查）：https://wiki.python.org/moin/TimeComplexity

14. 自我检查

能用三步口诀给简单代码标大 O；
能背出七级阶梯的 n=100 万量级对照，并说出 O(2ⁿ)/O(n!) 的典型场景信号；
能同时算清一段代码的时间账与空间账，并解释递归为什么会 RecursionError；
能区分 O、Ω、Θ，说出工程上为什么盯最坏情况；
能识别「隐藏循环」「函数调用代价」「最好情况当日常」三类误判；
已完成本文三组实验与两道遮代码自检，并记录自己的实测数字。

本章总结

大 O 是代价的增长趋势语言：常数与低阶项忽略，只看 n 扩大时的走向。时间之外还有空间这本账——递归把状态叠在调用栈上，深度超限直接崩，而不是慢；最好/最坏/平均三种口径里，工程承诺永远按最坏兑现。七级阶梯（O(1) 到 O(n!)）覆盖日常判断，timeit 让每个判断都可亲手验证。下一页从最基础的数据组织——数组——开始，把这套语言用到具体结构上。

下一步

进入数组与动态数组：为什么数组随机访问是 O(1)，扩容为什么是均摊 O(1)，以及连续内存在缓存层面的额外红利。

算法分析基础：两段代码差在哪

前置知识#

学习目标#

1. 你现在要解决什么问题#

2. 最小可运行实验：亲手计时#

3. 发生了什么：为什么只谈趋势#

4. 核心概念一：七级阶梯与生活对照#

5. 核心概念二：空间复杂度——同一份代码的第二本账#

6. 核心概念三：最好、最坏与平均——O、Ω 与 Θ#

7. 调试实录：判复杂度的三个常见误判#

8. 修改实验#

9. 小练习#

10. 动手实践：遮代码自检#

11. 什么时候应该 / 不应该死磕复杂度#

12. 与之前和之后的知识的关系#

13. 官方文档#

14. 自我检查#

本章总结#

下一步#

前置知识

学习目标

1. 你现在要解决什么问题

2. 最小可运行实验：亲手计时

3. 发生了什么：为什么只谈趋势

4. 核心概念一：七级阶梯与生活对照

5. 核心概念二：空间复杂度——同一份代码的第二本账

6. 核心概念三：最好、最坏与平均——O、Ω 与 Θ

7. 调试实录：判复杂度的三个常见误判

8. 修改实验

9. 小练习

10. 动手实践：遮代码自检

11. 什么时候应该 / 不应该死磕复杂度

12. 与之前和之后的知识的关系

13. 官方文档

14. 自我检查

本章总结

下一步