L10结束于三个问题：实现要做多少工作、失败归谁处理、凭什么相信它是对的。本讲分别回答。

分两个45分钟；后面32页完整机制与旧例供课后查阅，不计入课堂必讲。

三者看起来无关，其实是同一个问题的三个面：凭什么说这段程序真的可用。

真实世界不承诺输入合法、数据干净、规模不大；这一讲给三种证据。

先不给代码，只给两种实现在一小段和完整数据上的表现。让学生说出判断依据。

计时是最直接的做法，但下一页用一道题把这个依据变成可检验的问题。

开场只考已经学过的循环与函数，不涉及复杂度记号。

先让学生动手数一遍，第9页回顾原题分布，不重复提交。

顺序由问题推进：先量化成本，再处理可预期的失败，然后检查不该发生的错误，最后用在本周作业上。

没有单独的AI政策页；第11周实验按Level 1要求声明。

本讲与第12周同属第五部分。本讲负责成本、异常与测试；第12周处理随机数、编码与文件。

先建立「工作量」这个可比较的量，再谈失败和证据。

先承认计时的作用，再说明它为什么不能单独作为比较依据。

替代方案是数步数：只依赖输入规模，不依赖机器。

同一段代码在不同条件下差别明显，计时给出的结论不稳固。

所以需要一个与机器无关的量：数基本操作的次数。下一页给出这个量。

回顾开场题：内层一共 6 次，就是把每一步加起来的结果。

步数只依赖输入规模。把 n+2 换成 n²，两者的差别在下一页用表讲清楚。

只关心 n 很大时的趋势，所以去掉低阶项和常数系数。

这是描述增长形状，不是精确步数：O(n) 不意味着正好 n 步。

这张图是本讲的坐标系：阶数越高，曲线越早离开底部。右边一列例子全是学生已经写过的代码，不是新知识。

下一页给一个本机的量级锚点，让他们能估算一个规模跑不跑得完。

这个数字是 Python 级循环的口径：一秒约七千万次循环体。

由此可以估算：n=10^6 的 O(n) 约 0.01 秒；同样规模的 O(n^2) 是 10^12 步，要跑几个小时。内置函数在 C 中执行，会快一到两个数量级，所以这个锚点是下界。

先投票：一个常数很大的线性循环，和一个什么都没有的常数操作，谁更贵。

本页只看单次调用的表面，下一页让 n 变大再比较。

n

这些是常见结论，不是全部实现细节。重点记两条：列表头部插入删除是线性，字典与集合的键查找是常数。

下一页用实测验证第二条，这正是 L06 容器选型那句结论的依据。

n

先投票，并说出理由。学生最常见的理由是「字符串不可变，所以每次都复制」。

下一页用三种写法实测校正这个直觉的适用范围。这是本讲最重要的一处修订。

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

原因是 CPython 对只有单一引用的字符串可以原地扩展。结论必须写成「取决于有没有别的引用」，不能写成「循环拼接一律平方级」。写代码仍然推荐 join，因为它不依赖这条实现细节。

L07 写过二分查找，当时把复杂度留到这里。每比较一次候选范围减半，问题是从 n 降到 1 要除几次 2，答案是对数。

十亿个元素最多三十次比较，这就是对数复杂度，也是排好序的数据值钱的原因。

同样的记号用来描述内存占用，这一点学生第一次见。

生成器如何把 O(n) 空间降回 O(1) 在 L13 讨论，这里先建立概念。

顺序不能颠倒：内置函数快是常数变小，救不了错的算法。本机实测 sum(range(2*10^6)) 比手写循环快约 2.4 倍，两者都是 O(n)。

这就是「先降阶、再优化常数」的具体含义，也是 Knuth 那句话的落点。

检查是否理解折半次数就是对数，不涉及新记号。

第19页已经给出方法，本题验收；下页讲评原题分布。

从成本转到失败。先区分可预期的外部问题和不该发生的内部错误，这一区分在第三部分决定用异常还是断言。

顺序不能颠倒：先看得见的崩溃，再谈不声不响的错。

这段代码语法完全正确，Python 顺利编译了，运行时才出错。这种错误叫异常。

回溯的最后一行给出类型与消息；不处理的话程序在这里终止，后面的语句一行都不执行。

上一页是除零，这一页再补两种最常见的运行时错误。

共同点是名字和类型都检查不出来，必须真的执行到那里才知道。下一页开始处理它们。

try 体正常执行时跳过 except；一旦抛出异常，立刻跳到匹配的分支。

这正好解决了 L03 留下的问题：那时候说输入非数字程序会崩，L11 讲怎么办。

捕获具体的类型，程序可以给用户一句有用的提示并继续。

下一页把三种不同的失败放进同一段 try，说明分支顺序。

先投票：宽类型写在前面、具体类型写在后面，捕获到的会是哪一个。

常见直觉是「更具体的会先匹配」。下一页用实测结果回答，并说明裸 except 为什么更糟。

实际先打印 cleanup 再返回 general。异常按书写顺序从上到下匹配，宽类型在前会遮住后面的具体类型。

裸 except 等价于捕获一切，包括拼写错误和 KeyboardInterrupt；要兜底就写 except Exception as error 并把消息打印出来。

else 只在 try 体没有抛异常时执行，放成功之后才该做的事；finally 无论如何都执行，放清理工作。

实测四行输出说明两条路径的差别：成功走 else 和 finally，失败走 except 和 finally。下一页检查 finally 里的 return。

先投票：try 里已经准备好返回 from try，finally 里又写了一个 return，函数最终返回什么。

常见答案是 from try。下一页给出实测结果，并说明 finally 里的 return 还会抑制正在传播的异常。

实际返回 42，而不是抛出 ZeroDivisionError：finally 里的 return 既覆盖返回值，也丢弃待传播的异常。

finally 在任何离开 try 的路径上都执行，这正是清理代码不要顺手写 return 的理由。with 的异常抑制是同一类边界。

需要调用方无法忽略时用 raise。返回 None 容易被忽略，错误会在离原因很远的地方才爆发。

抛异常立刻停下，回溯直接指向出问题的位置。本周实验里的 ValueError 就是这条规则的用法。

自定义异常继承 Exception，L10 的继承在这里派上用场。

好处是调用方能精确捕获这一种失败，而不是笼统地抓 ValueError。异常类保持简单，通常只带需要的信息。

两个45分钟的分界。上半节讲了成本、异常与清理。

下半节讲假设检查、测试的写法，以及素数五法的规模与成本。

with 保证退出时执行清理，等价于写好的 try/finally。

只有 __enter__ 成功返回，__exit__ 才会被调用；块里抛异常，文件同样关闭。文件操作的完整内容在 L12。

Python

同时检查分支顺序与 finally 的位置。所有语法在第34页前都已教完。

下页讲评原题分布，不再发同题。

进入第三种失败。断言把「我以为一定成立」写成可执行检查，测试把观察值与期望值比较。

两者都指向证据，但一个检查程序自身的前提，一个检查对外行为。

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

用法是描述「这里必须成立」，不是给用户看的提示。下一页检查它在优化模式下的行为。

同一个函数，一次在普通模式下运行，一次加上 -O 参数。先预测两次的结果有什么不同。

常见直觉是「关掉断言只是少了一层检查」。下一页给出两次运行的实际结果，其中一次会以除零错误结束。

正常模式下断言生效，对空列表抛出 AssertionError；-O 模式下断言被跳过，函数继续执行到除零，抛出的变成 ZeroDivisionError。

所以断言不能校验用户输入。另外 assert (条件, 消息) 写成元组永远为真，检查会完全失效。

这道题检查断言表达式里的副作用：条件看起来成立，实际却已经改了状态。

全部语法已教，下页讲评。

断言把「输入必须有序」这类前置条件写成可执行检查，比注释可靠，因为注释会过期。

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

L08 用检查循环比对期望值，pytest 把这套动作标准化。规则只有三条，先记住文件名与函数名都要以 test_ 开头。

下一页给一次真实运行的输出，包括一个故意写错的用例。

这段输出来自真实执行：三个用例通过，一个失败。

输出给出三件事：哪个用例失败、它期望什么（ZeroDivisionError）、实际发生什么（ValueError）。这正是它比手写循环有用的地方。完整诊断格式与 -v、-k 参数在参考区。

实用起点是每个 if 分支至少走一遍。

L08 的边界清单在这里继续使用：AI 最常漏的仍然是「空」和「一个」。下一页把这张表用在一个别人写的模块上。

本周实验给的模块，三个函数各有一句文档，都没有说空字符串怎么办。

实测三个里有两个在空串上失败。文档没有约定的输入，正是容易出问题的地方。完整模块与文档在讲义。

先让学生给出数字和理由，再往下看。

这是「文档与实现不一致」的例子，也是测试存在的意义：先把期望写下来，再看实现是否满足。

实测 word_count("") 返回 0 正常；longest_word("") 抛 ValueError，average_word_length("") 抛 ZeroDivisionError。

原因分别是 max() 收到空序列和除数为零。测试的作用是先把期望写下来，再看实现是否满足。

平台做的就是把返回值和期望值比较，和上面 clamp 的检查循环是同一件事。

用 print 的函数返回 None，比较永远为假——这就是从 L03 起那句「函数要 return 不要 print」背后的机制，不是一条孤立的规则。

Q4

这是本周个人作业 2 的理论依据。前三种同阶、常数不同；筛法降了阶，代价是一份长度为 n 的标记数组。

复杂度只说明增长形状，实际耗时还要看常数，下一页用实测说明。

平方根剪枝与 6k±1 在同一阶，常数差约三倍；筛法一直最快，代价是那份 O(n) 空间。

报告要求先验证正确性再计时，慢方法允许选可完成的规模，但不能换成另一种算法冒充。

两题分别检查「缓存要求可哈希的参数」与「键必须唯一确定子问题」。

全部语法已教，第57页后讲评。

L07 发现朴素斐波那契重复计算量巨大，并把修复留到这里。图中同一个 fib(3)、fib(2) 被反复算，这就是调用次数远超结果的原因。

根源是同一个子问题被算了无数遍，解决办法是把算过的记下来。

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

原因是 ways 有两个会变的参数：只看 amount，会把「用前两种面额凑出 10 分」和「用全部四种凑出 10 分」当成同一个状态，于是缓存了一个属于别的子问题的值。下一页对照两种键。

换成元组键之后结果正确，缓存里的条目数正好是所有 (amount, index) 的合法组合数。

记忆化把指数级降到线性，代价是存下这些结果，这是又一处空间换时间。

标准库提供现成实现，装饰器本身在 L14 展开。本页只讲三件事：它能用、参数必须可哈希、maxsize 会限制条目数。

cache_info 给出命中与未命中次数；第二次算 fib(10) 时命中数增加，说明没有重新递归。Q5 的 TypeError 正是这条要求的直接后果。

按现行配置第10周启动、第11周提交，三份个人作业各占 5%。

MR 的确定性只在本题域内成立，不能外推到任意大整数。完整参考解不公开，助教核对各方法是否为真实实现。

差别在适用规模与空间：筛法要一份长度为 n 的标记数组，适合一次问出整个区间；Miller-Rabin 每次只判断一个数，空间是常数。

本周任务限定 n ≤ 100000，三种试除法都能完成，区别在耗时，不在阶数。

七项沿用现稿任务，接口在实验页写明，提交页就地展开题面。

第11周按 Level 1 要求提交使用声明；本地保存与验收不等于线上提交。

六条都对应本讲实测过的代码，不是风格偏好。

最后一条是第48页的直接结论，也是 L08「先写测试」在本周的具体要求。

回到第2页的三种失败：太慢用增长阶回答，会崩用失败边界回答，悄悄算错用可执行检查回答。

第12周处理随机数、编码与文件，那里的输入更不干净，本讲的三种证据会继续使用。主线到此结束，后面32页供课后查阅。

参考保留完整的异常机制、旧稿的复杂度与哈希知识、素数五法的完整实现与提交规格。

片段标明依赖，长程序链接完整讲义，不设独立运行按钮。

同一个算法在同样规模下，不同输入的耗时可能不同。

本课不特别说明时都按最坏情况分析；平均情况的结论离开了分布假设就不成立。

n + 2 确实被 n² 从上方界住，所以写成 O(n²) 不算错，只是不紧。

平方根剪枝与 6k±1 就是「同阶、只差常数」的例子。

400 项系数时两种写法实测相差约 37 倍，阶数相同、常数不同。

这不是新算法，是同一个式子的两种写法，值得知道有这个形式。

这两条假设推出上面全部结论，是第15页那张表的依据。

n 翻倍时间大约翻四倍，因为每一次插入本身是线性操作，而它被调用了 n 次。旧稿手写的 insert/find/remove 实现保留在讲义。

字典和集合的 O(1) 来自位置函数，代价是预留空间。

本课不要求你设计哈希函数，只要求知道契约；碰撞的存在不否定平均情况下的常数查找。

规则是「相等的对象必须有相等的哈希值」，1、1.0、True 三者相等，所以哈希值相同。

可变容器不可哈希：内容会变，如果能当键，改内容就会让键找不到。定义 __eq__ 而不定义 __hash__ 的类，实例自动变成不可哈希。

要让自己写的对象当字典键，就得同时给出一致的 __eq__ 和 __hash__。

实践中多数情况用一个元组当键就够了，不必自己实现哈希。

保留原来的 while 实现与边界说明，和 L07 的递归版本对照。

排序前提在第三部分的断言里写成了可执行检查。

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

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

fib(28) 记忆化后调用 55 次、缓存 27 个条目，因为只有 28 个不同的子问题。

字典与列表两种写法在讲义里都给了，区别只在查找常数和内存的实际使用量。

同样算 fib，迭代版本只用两个变量，递归版本要保留整条调用链。

L13 讲生成器时，会把「一次只产生一个值、不建整个列表」这条思路用到极致。

函数记下信息后用裸 raise 继续往上抛，回溯保留，最终由调用方决定怎么处理。

返回值与抛异常的选择在这里一目了然：返回 None 的话，打印出来的是一句话；抛异常的话，调用方必须表态。

同一段 try 的多个 except 不捕获彼此抛出的异常，它会往上走。

需要兜底时先记录再 raise，这样既留下信息又没有把错误吞掉。

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

L09 的 Temperature 改成抛异常后，set_celsius 从返回 False 变成抛 TemperatureError，调用方就不能再忽略返回值了。

with

第三行是最容易犯的错：多写一对括号，检查就完全失效。

第四行见 Q4：assert not events.append("hit") 通过，但元素已经进了列表。

实测：正常模式下 __debug__ 为 True，-O 下为 False，断言被跳过。

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

断言失败意味着程序有 bug，正确的做法是让它崩掉，这样才看得到回溯。

开发期与生产期的差别就在这里：断言是开发期的检查。

浮点比较值得单独说：0.1 + 0.2 == 0.3 实测为 False，二进制小数存不下这三个数。

要比较浮点结果就用 pytest.approx 或给一个容差。

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

讲义保留可单文件运行的说明，同时给出真实 pytest 输出，不手写终端文本。

平台调用你的函数，把返回值和期望值比较。

这就是从 L03 起那句「函数要 return 不要 print」背后的机制。

每个分支至少一个用例。

让 AI 帮忙补用例时，仍然要自己先把这张表列一遍：L08 说了，「空」和「一个」正是最容易漏掉的两类。

文档只说了「返回最长的单词」，没有约定空字符串。

测试的价值就是把没约定的输入摆出来，让差异变成可见的事实。

for...else 在这里正好合用：循环没有被 break 打断，就是一个因子都没找到，p 是素数。

两种写法在 n ≤ 2 时都返回 0。

阶数没变，只是试除次数少了约三分之二。

这是「同阶不同常数」最直观的例子，和第67页的渐近含义呼应。

筛法一直最快，代价是那份长度为 n 的标记数组。

小范围时它的初始化成本相对更高，这一点在实测表里也能看出来。

适用范围必须说清楚：用底数 2 和 3，n < 1,373,653 时结论是确定的，本题域内 n ≤ 100000 成立。

超出这个界之后，这几个底数只是概率性的证据，不能称对任意大整数确定。

报告里的耗时要有可比性，所以这几条是硬要求。

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

按现行配置覆盖第10、11周，截止读统一校历。

完整参考解不公开，助教核对各方法是否为真实实现；报告里要写清楚各自能完成的规模。

原始分不改学期权重或日历；测试题的评分不只看测试是否通过，也看是否覆盖了空、单个、边界和异常。

本讲的三种证据会继续使用：增长阶比较算法，失败边界划分责任，可执行检查写下期望。

第12周处理随机数、编码与文件，那里的输入更不干净，正好检验本讲的失败边界与测试写法。