程序辜负你的三种方式

到目前为止，你写的程序都活在理想世界里：输入总是合法的，数据总是干净的，规模总是很小。

真实世界不是这样。程序会以三种方式让你失望：

三件事看起来无关，其实是同一个问题的三个面：你怎么知道你的程序真的能用？

---

I. 太慢：复杂度

为什么不用秒表

想知道一个算法快不快，最直接的想法是跑一下计时：

import time

def sum_to(n: int) -> int:
    total = 0
    for i in range(n):
        total += i
    return total

for n in [10_000, 100_000, 1_000_000]:
    t = time.perf_counter()
    sum_to(n)
    print(f"n = {n:>9,}  耗时 {time.perf_counter() - t:.4f} 秒")

这个数字有用，但它不能拿来比较算法，因为它取决于机器快慢、当时 CPU 在忙什么、Python 版本、有没有开着别的程序。

我们需要一个与机器无关的度量。

数步数，而不是数秒

换个思路：数这个算法要执行多少次基本操作。基本操作指的是加减乘除、比较、赋值、访问下标这类一步就能做完的事。

def sum_to(n):
    total = 0            # 1 步
    for i in range(n):   # 循环 n 次
        total += i       # 每次 1 步
    return total         # 1 步

总共大约 n + 2 步。

再看一个：

def has_duplicate(items):
    for i in range(len(items)):        # n 次
        for j in range(len(items)):    # 每次又 n 次
            if items[i] == items[j]:   # 1 步
                ...

这是 n × n = n² 步。

关键差别是：当 n 变大时，它们的增长速度完全不同。

n 翻十倍，第一个也翻十倍，第二个翻一百倍。

大 O 记号

我们只关心 n 很大时的增长趋势，所以：

• 只保留增长最快的那一项：n² + 3n + 5 → 看 n²
• 忽略常数系数：5n 和 100n 都记作 n

写成 O(...)，读作“大 O”：

• n + 2 → O(n)，线性
• n² → O(n²)，平方
• 3 → O(1)，常数（和 n 无关）

为什么可以忽略常数？因为增长的阶数一旦不同，常数再大也追不上：

for n in [10, 100, 1000, 10000]:
    linear = 100 * n
    quadratic = n * n
    winner = "O(n) 更少" if linear < quadratic else "O(n²) 更少"
    print(f"n={n:>6}  100n = {linear:>10,}   n² = {quadratic:>12,}   {winner}")

n 超过 100 之后，O(n) 就再也不会输了。这就是为什么阶数比常数重要。

常见的复杂度

从快到慢：

import math
print(f"{'n':>8} {'log n':>7} {'n':>8} {'n log n':>11} {'n²':>14}")
for n in [10, 1000, 100000]:
    print(f"{n:>8} {math.log2(n):>7.1f} {n:>8,} {n*n*math.log2(n):>11,.0f} {n*n:>14,}")

Python 各种操作的复杂度

这张表很实用，值得记住：

这解释了 L6 讲容器选型时那句“列表查找慢、集合查找快”：

import time

n = 30_000
data_list = list(range(n))
data_set = set(data_list)

t = time.perf_counter()
for x in range(0, n, 100):
    x in data_list
list_time = time.perf_counter() - t

t = time.perf_counter()
for x in range(0, n, 100):
    x in data_set
set_time = time.perf_counter() - t

print(f"列表 in: {list_time:.4f} 秒")
print(f"集合 in: {set_time:.6f} 秒")
print(f"差 {list_time / set_time:,.0f} 倍")

列表的长度翻倍，查询时间大约翻四倍；集合几乎没有变化。这一次结论有数据支持。

循环里拼字符串到底慢不慢

Lab 4 的三角形题和很多教材都说过：循环里 s += w 是 O(n²)，要改成 join。这句话需要限定条件。

先看实测：

import time

words = ["hello"] * 80_000

t = time.perf_counter()
s = ""
for w in words:
    s += w
plain = time.perf_counter() - t

t = time.perf_counter()
keep = []
for w in words:
    keep.append(keep[-1] + w if keep else w)
kept = time.perf_counter() - t

t = time.perf_counter()
s2 = "".join(words)
joined = time.perf_counter() - t

print(f"普通 s += w:      {plain:.5f} 秒")
print(f"每次留下中间结果: {kept:.4f} 秒")
print(f"join:             {joined:.6f} 秒")
print(f"结果一样吗: {s == s2 == keep[-1]}")

实测结果是：普通 s += w 循环与 join 在同一量级，而每次都把中间结果留活的写法慢了三个数量级。

原因在于 CPython 的一个实现细节：当一个字符串对象只有 s 这一个引用时，s += w 可以原地扩展，不必每次复制整个旧串。一旦中间结果被别的名字或容器引用，这个优化就不再成立，每次都只能造新串、复制旧内容，总代价退化成平方级。

结论要写成“取决于有没有其他引用”，不能写成“循环拼接一律平方级”。 写代码时仍然推荐 join：它不依赖这条实现细节，在任何实现和任何引用情况下都是线性的。

二分查找为什么是 O(log n)

L7 写过二分查找，当时说“复杂度留到 L11”。现在补上。

每比较一次，候选范围就减半：n → n/2 → n/4 → … → 1。

问：除以多少次 2 才能从 n 降到 1？ 答案就是 log₂ n。

import math
for n in [100, 1_000, 1_000_000, 1_000_000_000]:
    print(f"{n:>15,} 个元素，最多比较 {math.ceil(math.log2(n)):>2} 次")

十亿个元素，三十次比较。 这就是对数复杂度的威力，也是为什么排好序的数据这么值钱。

空间复杂度

同样的记号也用来描述内存占用。

# O(1) 空间：不管 n 多大，只用几个变量
def sum_loop(n: int) -> int:
    total = 0
    for i in range(n):
        total += i
    return total

# O(n) 空间：造了一个 n 长的列表
def sum_list(n: int) -> int:
    return sum([i for i in range(n)])

print(sum_loop(1000), sum_list(1000))

L13 讲生成器时，你会看到怎么把 O(n) 空间降回 O(1)。

怎么改进复杂度

按有效性排序：

1. 换算法：O(n²) 变 O(n log n)，这是数量级的改进
2. 换数据结构：列表查找换成集合，O(n) 变 O(1)
3. 避免重复计算：记忆化，第四节展开
4. 用内置函数：sum()、sorted()、"".join() 底层是 C 写的，比纯 Python 循环快一个数量级

import time
n = 2_000_000

t = time.perf_counter()
total1 = 0
for i in range(n):
    total1 += i
loop_t = time.perf_counter() - t

t = time.perf_counter()
total2 = sum(range(n))
builtin_t = time.perf_counter() - t

print(f"手写循环: {loop_t:.4f} 秒")
print(f"内置 sum: {builtin_t:.4f} 秒")
print(f"快 {loop_t / builtin_t:.1f} 倍（同为 O(n)，差在常数）")

---

II. 会崩：异常

语法对了，还是会出错

x = 10
y = 0
print(x / y)

这段代码语法完全正确，Python 也顺利编译了，但运行时出错了。这种运行时才发生的错误叫异常（exception）。

不处理的话，程序直接终止，后面的代码一行都不会执行。回溯的最后一行给出异常类型与消息，上面几行指出出问题的位置。

另外两种常见的运行时错误：

value = 4
print(value + spam * 3)

text = "2"
print(text + 2)

NameError 说明用了一个没有定义的名字；TypeError 说明两个类型不能这样组合。两者的共同点是：名字和类型都检查不出问题，只有真的执行到那一行才知道。

try / except

def safe_divide(a: float, b: float) -> float | None:
    try:
        return a / b
    except ZeroDivisionError:
        print("除数不能为零")
        return None

print(safe_divide(10, 2))
print(safe_divide(10, 0))
print("程序继续运行")

try 里的代码正常执行；一旦抛出异常，立刻跳到匹配的 except 分支。

捕获具体的异常

def parse_age(text: str) -> int | None:
    try:
        return int(text)
    except ValueError:
        print(f"「{text}」不是一个整数")
        return None

for s in ["18", "abc", "3.14", ""]:
    print(s, "→", parse_age(s))

这正好解决了 L3 留下的问题。那时候说“输入非数字程序会崩，L11 教你怎么办”，现在有了。

多个 except

def get_item(data: dict[str, list[int]], key: str, index: int) -> int | None:
    try:
        return data[key][index]
    except KeyError:
        print(f"没有键 {key}")
    except IndexError:
        print(f"下标 {index} 越界")
    except TypeError as error:
        print(f"类型不对: {error}")
    return None

d = {"a": [1, 2, 3]}
print(get_item(d, "a", 1))
print(get_item(d, "b", 0))
print(get_item(d, "a", 10))

最多只有一个分支会执行，按从上到下第一个匹配的算。

else 和 finally

def divide(a: float, b: float) -> None:
    try:
        result = a / b
    except ZeroDivisionError:
        print("   出错了")
    else:
        print(f"   成功，结果 {result}")     # 没出异常时才执行
    finally:
        print("   收尾工作")                  # 无论如何都执行

print("10 / 2:")
divide(10, 2)
print("10 / 0:")
divide(10, 0)

• else：try 里没有抛异常时执行。用来放“成功之后才该做的事”
• finally：不管怎样都执行。用来放清理工作，关文件、断开连接

finally 连 return 都拦不住：

def f() -> str:
    try:
        return "从 try 返回"
    finally:
        print("   finally 仍然执行了")

print(f())

raise：主动抛出

def set_age(age: int) -> int:
    if age < 0:
        raise ValueError(f"年龄不能为负: {age}")
    if age > 150:
        raise ValueError(f"年龄不合理: {age}")
    return age

print(set_age(18))
print(set_age(-5))

什么时候该 raise 而不是返回 None？

当调用方不应该忽略这个问题的时候。返回 None 很容易被忽略掉，然后错误传播到很远的地方才爆发；抛异常则立刻停下，回溯直接指向出问题的位置。

自定义异常

class InsufficientFunds(Exception):
    """余额不足。"""
    def __init__(self, balance: float, amount: float) -> None:
        super().__init__(f"余额 {balance}，无法取出 {amount}")
        self.balance = balance
        self.amount = amount


def withdraw(balance: float, amount: float) -> float:
    if amount > balance:
        raise InsufficientFunds(balance, amount)
    return balance - amount


try:
    withdraw(100, 500)
except InsufficientFunds as error:
    print("捕获到:", error)
    print("还差:", error.amount - error.balance)

自定义异常继承自 Exception（L10 的继承派上用场了）。好处是调用方能精确地捕获这一种错误，而不是笼统地抓 ValueError。

with：自动清理

# 手动版本，容易忘记关
handle = open("demo.txt", "w", encoding="utf-8")
handle.write("hello")
handle.close()

# with 版本，自动关
with open("demo.txt", "w", encoding="utf-8") as handle:
    handle.write("hello")
print("退出块后已关闭:", handle.closed)

# 块里抛异常，也一样会关
try:
    with open("demo.txt", encoding="utf-8") as reader:
        raise ValueError("块内出错")
except ValueError:
    print("异常退出后也已关闭:", reader.closed)

with 保证退出时执行清理，等价于一个写好的 try...finally。只有 __enter__ 成功返回，__exit__ 才会被调用。文件操作的完整内容在 L12。

该检查还是该捕获

两种风格：

d = {"a": 1}

# 风格一：先看再跳（Look Before You Leap）
if "b" in d:
    print(d["b"])
else:
    print("LBYL: 没有这个键")

# 风格二：先做再道歉（Easier to Ask Forgiveness than Permission）
try:
    print(d["b"])
except KeyError:
    print("EAFP: 没有这个键")

Python 社区偏好第二种（EAFP）。理由：

• 正常路径没有额外开销，异常只在真出错时才有代价
• 避免“检查完到使用之间状态变了”的问题
• 代码主干更清晰，正常流程一眼可见，异常处理在旁边

但简单的检查该做还是做。if not items: return 比包一层 try 清楚得多。

---

III. 悄悄算错：断言与测试

assert：检查你以为一定成立的事

def average(nums: list[float]) -> float:
    assert len(nums) > 0, "average 不接受空列表"
    return sum(nums) / len(nums)

print(average([1, 2, 3]))

assert 条件, 消息 的意思是：“我认为这里条件一定成立。如果不成立，说明我的程序有 bug，立刻停下。”

断言在优化模式下会被移除

print("__debug__ =", __debug__)
print("断言", "生效" if __debug__ else "被移除")

正常模式下 __debug__ 为 True，断言照常执行。加上 -O 参数后：

python3 -O myscript.py      # __debug__ 变成 False，所有 assert 消失

用上面那个 average 实测：正常模式对空列表抛出 AssertionError；-O 模式下断言被跳过，函数继续执行到 sum([]) / 0，抛出的是 ZeroDivisionError。

所以断言不能用来校验用户输入。 用户输入的校验必须用 if + raise，那条路径不会被优化掉。

断言不是异常处理

这是最容易混淆的一点，务必分清：

用断言给代码写文档

def binary_search(sorted_nums: list[int], target: int) -> int:
    assert sorted_nums == sorted(sorted_nums), "输入必须是已排序的"
    lo, hi = 0, len(sorted_nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sorted_nums[mid] == target:
            return mid
        if sorted_nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([1, 3, 5, 7], 5))
print(binary_search([1, 3, 5, 7], 4))

这条断言把“输入必须有序”这个前置条件写成了可执行的检查。比写在注释里强，注释会过期，断言不会。

后置条件同样可以写：返回的下标处确实是目标，或者返回 -1 且目标确实不在其中。

pytest：把测试正规化

L8 说过：判断代码对不对的依据是测试，不是“读起来合理”。当时我们手写了一个检查循环。现在把它规范化。

安装：

python3 -m pip install pytest

写测试的规则很简单：

• 文件名以 test_ 开头
• 函数名以 test_ 开头
• 用 assert 表达期望
• 期望抛异常时用 pytest.raises

假设你有 mymath.py：

# mymath.py
def add(a: int, b: int) -> int:
    return a + b

def divide(a: float, b: float) -> float:
    if b == 0:
        raise ValueError("除数不能为零")
    return a / b

对应的测试文件：

# test_mymath.py
import pytest
from mymath import add, divide


def test_add_two_positive():
    assert add(2, 3) == 5

def test_add_negatives():
    assert add(-1, -1) == -2

def test_divide_normal():
    assert divide(10, 2) == 5.0

def test_divide_by_zero():
    with pytest.raises(ZeroDivisionError):   # 期望它抛异常
        divide(10, 0)

注意最后一个用例是故意写错的：divide 抛出的是 ValueError，测试却期望 ZeroDivisionError。这样能看到失败时 pytest 给什么信息。真实运行结果：

$ python3 -m pytest -q
.F..                                                                     [100%]
=================================== FAILURES ===================================
_____________________________ test_divide_by_zero ______________________________

    def test_divide_by_zero():
        with pytest.raises(ZeroDivisionError):
>           divide(10, 0)

test_mymath.py:17:
    def divide(a: float, b: float) -> float:
        if b == 0:
>           raise ValueError("cannot divide by zero")
E           ValueError: cannot divide by zero

mymath.py:6: ValueError
=========================== short test summary info ============================
FAILED test_mymath.py::test_divide_by_zero - ValueError: cannot divide by zero
1 failed, 3 passed in 0.01s

输出了三件必须知道的事：哪个用例失败、它期望什么（ZeroDivisionError）、实际发生了什么（ValueError）。这正是 pytest 比手写检查循环有用的地方。

常用参数：

python3 -m pytest              # 跑所有测试
python3 -m pytest -v           # 显示每个测试的名字
python3 -m pytest -k divide    # 只跑名字含 divide 的

该测什么

回顾 L8 的边界清单，一个函数至少该测：

• 正常情况：典型输入
• 空输入：空列表、空字符串
• 单个元素
• 边界值：0、负数、最大最小
• 异常情况：非法输入是否正确抛出

def clamp(x: float, lo: float, hi: float) -> float:
    """把 x 限制在 [lo, hi] 范围内。"""
    if lo > hi:
        raise ValueError("lo 不能大于 hi")
    return max(lo, min(x, hi))


checks = [
    ("范围内", clamp(5, 0, 10), 5),
    ("小于下界", clamp(-3, 0, 10), 0),
    ("大于上界", clamp(99, 0, 10), 10),
    ("正好在边界", clamp(0, 0, 10), 0),
    ("上下界相等", clamp(7, 3, 3), 3),
]
for name, got, expected in checks:
    print(f"  {'通过' if got == expected else '失败'} {name}: {got}")

try:
    clamp(5, 10, 0)
    print("  失败：非法范围没有抛异常")
except ValueError:
    print("  通过：非法范围正确抛出 ValueError")

给别人的代码写测试

本周实验里有一个模块是“已经写好的”，你的任务不是改它，而是给它的文档描述写测试：

# textstats.py
def word_count(text: str) -> int:
    """数一数有多少个单词。"""
    return len(text.split())

def longest_word(text: str) -> str:
    """返回最长的单词。长度相同时取第一个。"""
    words = text.split()
    return max(words, key=len)

def average_word_length(text: str) -> float:
    """返回平均单词长度。"""
    words = text.split()
    return sum(len(w) for w in words) / len(words)

三个函数都写了一句文档，但都没有说空字符串怎么办。实测结果：

word_count("")             → 0
longest_word("")           → ValueError
average_word_length("")    → ZeroDivisionError

三个里有两个在空字符串上失败：max() 收到空序列会抛 ValueError，除以零会抛 ZeroDivisionError。

文档没有约定的输入，正是容易出问题的地方。 你不写这个模块，唯一的依据就是文档描述——测试的作用就是先把期望写下来，再看实现是否满足。

平台是怎么给你判分的

---

IV. 五种方法与记忆化

素数五法的成本

本周个人作业要在同一个区间上实现五种素数计数方法。它们的复杂度：

前三种是同一阶的不同常数；筛法降了阶，但要多一份长度为 n 的标记数组。

复杂度只说明增长形状，实际耗时还要看常数。 在本机、n = 100000、重复取最小值的实测：

（五种方法在 n = 2000 时都得 303，在 n = 100000 时都得 9592。计数必须完全一致，这是“先验证正确性再计时”的意思。）

平方根剪枝与 6k±1 在同一阶，但常数差约三倍；筛法一直最快，代价是那份 O(n) 的空间。只有在需要一次问出整个区间的素数个数时，筛法才划算；如果只是判断一个大数是不是素数，Miller–Rabin 的 O(1) 空间和 O(log³ n) 的代价更合适。

什么时候选哪一种

• 一次问很多个数、区间不大：筛法
• 只判断个别很大的数：Miller–Rabin
• 本周任务（n ≤ 100000）：三种试除法都能完成，区别在耗时，不在阶数

记忆化：把指数降到线性

L7 里我们发现朴素的斐波那契要调用二十多万次，并说“L11 讲怎么修”。

先看看重复计算到底有多严重：

fib(20) =     6765   calls =    21,891
fib(25) =    75025   calls =   242,785
fib(28) =   317811   calls = 1,028,457

n 加 3，调用次数大约翻 4 倍，而结果只增长到 3 倍左右。根源是同一个子问题被算了无数遍。

解决办法很直接：算过的记下来。

fib(28) = 317811, calls = 55, cache entries = 27

同样的结果，调用次数从 1028457 降到 55，缓存里只有 27 个条目。因为 fib 只有 28 个不同的子问题。

复杂度从 O(2ⁿ) 降到 O(n)，每个 n 只算一次。代价是要存 n 个结果，这是又一处空间换时间。

缓存键必须唯一确定子问题

把上面这套照搬到硬币组合题（L7 的 count_ways），很容易写错：

key = amount:            129
key = (amount, index):    11

正确答案是 11，只用 amount 作键得到 129。

原因：ways(amount, coins, index) 有两个会变的参数。只看 amount，会把“用前 2 种面额凑出 10 分”和“用前 4 种面额凑出 10 分”当成同一个状态，于是缓存了一个属于别的子问题的值。

缓存正确的两个前提：

1. 键能唯一识别子问题：所有会变的参数都要进键
2. 函数对相同输入总给相同输出：依赖当前时间、随机数或外部状态的函数不能缓存

正确版本的运行结果：

ways(100) = 2156, calls = 801, cache entries = 400

缓存键写成元组 (amount, index)，400 个条目正好是 (amount, index) 的合法组合数。

functools.lru_cache

Python 标准库有现成的装饰器（L14 会讲装饰器是什么）：

fib(10) = 55
cache_info: 8 命中 11 未命中 11 条目
再算一次 fib(10) = 55
再算之后命中数 = 9
fib(100) = 354224848179261915075

cache_info() 给出命中次数、未命中次数和当前条目数。第二次算 fib(10) 时命中数从 8 变成 9，说明它没有重新递归。

加一行 @lru_cache，指数变线性。 注意两点：

• 被缓存的参数必须可哈希。给它传列表会直接报错：

TypeError: unhashable type: 'list'

换成元组 total((1, 2, 3)) 就正常返回 6。这正是 Q5 的考点。

• maxsize 限制缓存条目数，maxsize=None 表示不限制。填一个数字就成了 LRU 淘汰策略，内存有上限但可能重新计算。

---

参考：完整机制、旧例与提交规格

这一节供课后查阅，不占课堂 90 分钟。

最坏、最好与平均情况

同一个算法在同样规模下，不同输入的耗时可能不同。例如在一列数里找某个值，目标在第一个位置和不在列表里，扫描长度差得很远。

• 最坏情况：所有输入里代价最大的那一次。本课如果不特别说明，都按最坏情况分析
• 最好情况：代价最小的那一次，通常没有参考价值
• 平均情况：对所有可能输入取期望。它需要假设输入服从什么分布，假设不成立结论就不成立

渐近记号的准确含义

O(f(n)) 是上界记号，不是精确步数。n + 2 记作 O(n)，但 n + 2 也同样是 O(n²)——因为它确实被 n² 从上方界住。我们通常写的是最紧的那个界。

两点容易误解的地方：

• 只在输入足够大、阶数不同的时候，忽略常数才是安全的
• 阶数相同时，常数就是唯一有意义的差别（平方根剪枝与 6k±1 就是这种情况）

多项式求值：同一个数学式子，不同的乘法次数

朴素写法逐项求幂：

def naive(x, coefficients):
    total = 0
    for power, c in enumerate(coefficients):
        total += c * x ** power
    return total

Horner 形式把求幂变成连续乘加：

def horner(x, coefficients):
    total = 0
    for c in reversed(coefficients):
        total = total * x + c
    return total

两者数学上完全等价，但 400 项系数时实测相差约 37 倍。差别不在阶数（都是 O(n)），在每次循环的乘法次数。

列表的内存模型

两条基本假设：

1. 元素连续存储
2. 下标与元素一一对应

这两条推出：a[i] 是 O(1)（一次地址计算），而 a.insert(0, x) 和 a.pop(0) 是 O(n)（后面所有元素都要挪一格）。本机实测插入到头部：

n 翻倍，时间大约翻四倍，符合线性操作被调用 n 次的平方级总代价。

哈希表

字典和集合的查找之所以是 O(1)，是因为它们用位置函数直接算出存放位置，而不是从头逐个比较。代价是空间换时间：哈希表要预留比元素个数更多的槽位。

碰撞是存在的，也有成熟的处理办法。本课不要求你设计哈希函数，只要求知道契约。

哈希契约

hash(1) == hash(1.0)     → True
hash(True) == hash(1)    → True
hash((1, 2))             → 可以
hash([1])                → TypeError
hash({"a": 1})           → TypeError

规则：

• 相等的对象必须有相等的哈希值。1 == 1.0 == True，所以三者的哈希值相同
• 可变容器不可哈希。列表和字典的内容会变，如果它们能进字典当键，改内容就会让键找不到
• 定义了 __eq__ 而没有定义 __hash__ 的类，__hash__ 会变成 None，实例不可哈希

如果确实想让自己写的对象当字典键，就要同时给出一致的 __eq__ 和 __hash__；通常更省事的做法是把它变成不可变对象，或者干脆用一个元组当键。

递归的成本

朴素递归斐波那契的调用次数实测：

调用次数大约是结果的 3 倍多，说明绝大多数调用都在重复算已经算过的东西。

递归深度也有上限。本机实测 sys.getrecursionlimit() 为 1000，超过会抛 RecursionError。所以朴素的 fib(2000) 不是慢，是直接崩；记忆化版本因为每次只往下走一层，反而没有深度问题。

记忆化的两种写法

字典缓存（子问题稀疏时更省内存）：

cache: dict[int, int] = {}

def fib(n: int) -> int:
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    result = fib(n - 1) + fib(n - 2)
    cache[n] = result
    return result

列表缓存（子问题密集时更快，但要有确定的上界）：

def fib(n: int, memo: list[int]) -> int:
    if memo[n] != -1:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

memo = [-1] * (n + 1)

两者都是 O(n) 时间、O(n) 空间。区别只在常数的查找代价和内存的实际使用量。

空间与递归的关系

递归函数每一层调用都要保存现场，所以朴素递归的 fib 同时占 O(n) 的栈空间。迭代版本用 O(1) 空间就能算完：

def fib_iter(n: int) -> int:
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

L13 讲迭代器和生成器时，还会把“一次只产生一个值、不建整个列表”这条思路用到极致。

raise 的几种形式

raise ValueError("消息")          # 用类加参数，最常用
raise ValueError                  # 只说类型，不带消息
raise                             # 裸 raise，重新抛出当前异常

裸 raise 只能在 except 块里用，作用是保留原来的回溯继续往上抛：

try:
    ...
except ValueError:
    print("记录一下")
    raise          # 交给上层处理，回溯不丢

异常链用 from 保留因果：

except KeyError as error:
    raise ValueError("配置缺少字段") from error

多分支与兜底

except (KeyError, IndexError):     # 元组形式，两类一起处理

同一段 try 的多个 except 不捕获彼此抛出的异常。所以在一个 except 块里再抛出的异常，不会被同组的其他分支接住，它会往上走。

需要兜底时，写成：

except Exception as error:
    print("未预期的问题:", error)
    raise

这样既记录了信息，又没有把错误吞掉。

自定义异常的层级

一个模块里定义多个相关异常时，常见的做法是先定一个基类再派生：

class ConfigError(Exception):
    """配置相关问题的基类。"""

class ConfigMissing(ConfigError):
    """缺少必填字段。"""

class ConfigFormat(ConfigError):
    """字段格式不对。"""

调用方可以选择只抓 ConfigError 把这一类全接住，也可以精确到某一个子类。L09 的 Temperature 改成抛异常后，接口从“返回 False”变成“抛 TemperatureError”，调用方就不能再忽略返回值了。

资源与系统错误

with 和自己写的 try/finally 达到同样效果，但 with 短得多。有一个边界：只有 __enter__ 成功返回，__exit__ 才会被调用；如果 __exit__ 返回真值，块内正在传播的异常会被抑制。文件对象正常关闭时返回假值，所以异常照常往外走。

sys.exc_info() 在 except 块里给出当前异常的 (类型, 值, 回溯) 三元组，主要用于日志。

float() 到底接受什么

旧讲义把 float("inf") 当成非法输入，实测不是这样：

所以“判断一个字符串是不是数字”不能靠猜格式，要么用 float() 试着转换并捕获 ValueError，要么明确写出你想要的格式。注意 float("nan") 之后 nan != nan，这一条在比较时会造成意外。

pytest 的约定与选项

测试文件通常放在同目录或 tests/ 子目录，名字以 test_ 开头。pytest 会自动发现它们，不需要手写注册。

浮点比较值得单独说：0.1 + 0.2 == 0.3 实测为 False，因为二进制小数存不下这三个数的精确值。要比较浮点结果就用 pytest.approx 或者在断言里给一个容差。

讲义里的示例与真实测试的区别

讲义里的代码块是单文件、可复现的，可以直接跑。pytest 不行：它需要发现文件和收集用例，所以本节的做法是把同一套思路写成检查循环，让学生看到机制；真正的 pytest 运行结果在本节第三部分引用了原文。

两者检验的是同一件事：期望值与实际值不一致时，给出足够的信息定位问题。

边界清单

每个分支至少一个用例。用 AI 帮忙补用例时，仍然要自己先把这张表列一遍——L8 说了，“空”和“一个”正是最容易漏掉的两类。

textstats 在测试下的实际行为

文档只说了“返回最长的单词”“返回平均长度”，没有约定空字符串。测试的价值就在于把这些没约定的输入摆出来，让差异变成可见的事实，而不是先读实现再写一个必然通过的测试。

素数五法的完整说明

暴力试除

def count_primes_brute(n: int) -> int:
    count = 0
    for p in range(2, n):
        for d in range(2, p):
            if p % d == 0:
                break
        else:
            count += 1
    return count

for...else 在这里的用法：循环没有被 break 打断时执行 else，也就是“一个因子都没找到”。复杂度 O(n²)。

平方根剪枝

def count_primes_sqrt(n: int) -> int:
    count = 0
    for p in range(2, n):
        d = 2
        while d * d <= p:
            if p % d == 0:
                break
            d += 1
        else:
            count += 1
    return count

如果 p 有因子，至少有一个不超过 √p，所以试到 √p 就够。复杂度 O(n√n)。

6k±1 剪枝

先排除 2 和 3 的倍数，剩下的素数都形如 6k±1，于是因子候选只剩 5, 7, 11, 13, …：

def count_primes_6k(n: int) -> int:
    if n <= 2:
        return 0
    if n <= 3:
        return 1
    count = 2                      # 2 和 3
    for p in range(5, n):
        if p % 2 == 0 or p % 3 == 0:
            continue
        d = 5
        while d * d <= p:
            if p % d == 0 or p % (d + 2) == 0:
                break
            d += 6
        else:
            count += 1
    return count

阶数没变，还是 O(n√n)，但试除的次数少了约三分之二，实测快约三倍。

埃氏筛

def count_primes_sieve(n: int) -> int:
    if n <= 2:
        return 0
    flags = [True] * n
    flags[0] = flags[1] = False
    p = 2
    while p * p < n:
        if flags[p]:
            for multiple in range(p * p, n, p):
                flags[multiple] = False
        p += 1
    return sum(flags)

从 p * p 开始标记（比它小的倍数已经被更小的素数标过了），复杂度 O(n log log n)，空间 O(n)。

Miller–Rabin

先把小情形处理掉，再把 n−1 写成 d × 2ʳ，对底数 a 检验 a^d mod n：

def is_prime_mr(n: int) -> bool:
    if n < 2:
        return False
    for base in (2, 3):
        if n == base:
            return True
        if n % base == 0:
            return False
    d, r = n - 1, 0
    while d % 2 == 0:
        d //= 2
        r += 1
    for base in (2, 3):
        x = pow(base, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = x * x % n
            if x == n - 1:
                break
        else:
            return False
    return True

适用范围必须说清楚：用底数 2 和 3，当 n < 1,373,653 时结论是确定的。本题域内 n ≤ 100000，成立。但不能外推到任意大的整数——超出这个界之后，这几个底数就只是概率性的证据。

pow(base, d, n) 是内置的三参数幂，做模幂运算，每次检验是 O(log³ n)（位数是 log n，模幂是 O(位数³) 级别）。空间 O(1)。

公平计时的要求

报告里的耗时要有可比性，所以：

• 先验证正确性再计时。五种方法在相同小规模上必须得到相同的计数
• 固定规模、同一台机器、注明环境
• 预热后重复几次取最小值，避免偶然的调度抖动
• 慢方法允许选一个能完成的规模（比如暴力法只测到 2000），但不允许换成另一种算法冒充

本节的数字都来自构建环境一次测量，只用来比较量级和倍数，不承诺在你的机器上得到同样的秒数。

个人作业 2 的规格

按现行配置，个人作业 2 覆盖第 10、11 周，截止读统一校历，三份个人作业各占 5%。完整参考解不公开，助教核对各方法是否为真实实现。

Lab 11 的七个入口

测试题的评分不只看测试是否通过，也看是否覆盖了空、单个、边界和异常这四类输入。本周实验按 Level 1 要求提交使用声明。

---

小结

复杂度

• 用基本操作的步数衡量算法，与机器无关
• 大 O 只保留最高阶项，忽略常数，因为阶数不同时常数追不上
• 常见阶：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
• 记住 Python 的操作复杂度：列表 in 是 O(n)，集合和字典是 O(1)
• 循环里 += 拼字符串的成本取决于有没有别的引用；写代码时用 join，它不依赖实现细节
• 记忆化把重复子问题的递归从 O(2ⁿ) 降到 O(n)，键必须包含所有会变的参数
• 内置函数快是常数小，救不了错的算法。先降阶，再优化常数

异常

• 语法正确的代码仍会在运行时出错，这叫异常
• try / except 具体类型 / else（没出错时）/ finally（总是执行）
• 永远不要写裸的 except:
• raise 主动抛出；自定义异常继承 Exception
• with 保证清理，等价于写好的 try...finally
• Python 偏好 EAFP（先做再道歉）而不是 LBYL

断言与测试

• 异常处理外部的、可预期的问题；断言检查内部的、不该发生的情况
• 不要捕获 AssertionError，断言失败就该崩
• 断言在 -O 模式下会被跳过，所以不能用来校验用户输入
• assert (条件, 消息) 写成元组永远为真；断言表达式里不要写副作用
• pytest：test_ 开头的文件和函数，用 assert 表达期望，pytest.raises 测异常
• 实验平台就是调用你的函数比对返回值，所以必须 return
• 每个函数至少测：正常、空、单个、边界、异常

练习

1. 判断下面每个函数的时间复杂度，并说明理由：

   def f1(n): return sum(range(n))
   def f2(a): return [x for x in a if x in a]
   def f3(a): return sorted(set(a))
   def f4(n):
       count = 0
       i = n
       while i > 1:
           i = i // 2
           count += 1
       return count

2. 把 L7 里你写的 count_ways（硬币组合）加上记忆化，测量加速比。注意键要包含哪些参数。
3. 写一个 safe_int(text: str, default: int = 0) -> int，转换失败时返回默认值而不是崩溃。只捕获具体异常。
4. 下面的代码有什么问题？改对它：

   def process(filename):
       try:
           f = open(filename)
           data = f.read()
           return int(data)
       except:
           return 0

5. 给 Lab 9 你写的 Stack 类补一套 pytest 测试，至少覆盖：空栈、单元素、多元素、空栈 pop 的行为。
6. 用 assert 给 L7 的 binary_search 加上前置条件和后置条件（提示：后置条件可以检查“返回的下标处确实是 target，或者返回 -1 且 target 确实不在里面”）。
7. 实测一下：用 time.perf_counter() 测量 list.insert(0, x) 和 list.append(x) 各执行 10000 次的耗时，验证 O(n) 和 O(1) 的差别。

本讲的配套上机题在 Lab 11，个人作业在 个人作业 2。

来源

• Python 3.13 复合语句：try / except / else / finally / with 的语义
• Python 3.13 内置异常：异常层级与常见类型
• functools.lru_cache
• Miller–Rabin 素性检验：小范围确定性底数界