会写 Python 语法，和能为一个问题选择合适的方法，是两种不同的能力。本章从一个可以手工执行的小例子出发，区分问题、算法、程序与数据结构。
算法描述解决问题的步骤；程序用一种语言把这些步骤实现出来。数据的组织方式会影响步骤的成本。
1. 先写清问题，再动手编程
假设输入是一列整数，任务是返回最大值。输入可以为空吗？重复最大值需要返回一个值还是所有位置？允许负数吗？这些约定属于问题规格，不能等代码写完后才猜。
本章约定：输入是有限、非空的整数列表，返回最大值；空列表抛出 ValueError。例如 [3, 1, 8, 2] 返回 8，[-5, -2] 返回 -2。
2. 算法不是某一种编程语言
用自然语言就能描述找最大值：先记住第一项，逐一读后面的项，遇到更大的就更新记录，读完后交出记录。这套步骤可以用 Python、C，或者纸笔实现。它和某一份源代码并不是同一个概念。
算法需要明确的步骤、可接受的输入与可验证的结果。在本教材的有限输入问题中，还需要在有限步骤后结束。
3. 把步骤翻译成 Python
def maximum(values):
if not values:
raise ValueError("输入不能为空")
best = values[0]
for value in values[1:]:
if value > best:
best = value
return best
print(maximum([3, 1, 8, 2])) # 8
上面的切片会额外复制列表。若希望只保留常数额外空间，可用下标循环：
def maximum_indexed(values):
if not values:
raise ValueError("输入不能为空")
best = values[0]
for i in range(1, len(values)):
if values[i] > best:
best = values[i]
return best
两种实现都比较 n−1 次，时间 O(n)；切片版额外空间 O(n)，下标版额外空间 O(1)。语言细节可能改变空间成本。
4. 用循环不变式解释正确性
在处理完前 k 项后，best 是前 k 项中的最大值。
- 初始化：只看第一项时，这个结论成立。
- 保持：读入下一项，保留旧最大值或用更大的新项替换，结论仍成立。
- 结束：全部 n 项处理后，
best就是整个列表的最大值。
这种从初始化、保持到结束的推理，比“试了几个数据都对”更有解释力。测试用来发现错误，不能穷尽证明所有输入。
5. 错误的初始化为什么危险？
如果写 best = 0，对全负数输入 [-5, -2] 就会错误地返回 0。0 不属于原输入。用第一项初始化，并单独处理空列表，可避免偷偷假设数据非负。
“常见数据能跑通”和“在约定范围内都正确”是不同要求。
6. 算法与数据结构一起设计
同样是查找姓名，列表可逐项扫描，字典可以按键访问，有序数组可以二分搜索。对外都是“根据姓名找到记录”，内部组织与成本不同。
| 组织方式 | 查找方式 | 典型查找成本 | 额外前提 |
|---|---|---|---|
| 未排序列表 | 从头扫描 | 最坏 O(n) | 无需预先有序 |
| 有序列表 | 二分缩小范围 | O(log n) | 键有序、可快速访问中间项 |
| 哈希字典 | 根据哈希定位 | 平均 O(1)，最坏可 O(n) | 键可哈希、维护冲突与空间 |
这里的操作成本基于常规模型，键本身的比较或哈希成本也可能需要计入。
7. 时间和空间的取舍
反复查询一批记录时，可以先建立索引，用额外空间减少重复扫描；如果只查一次，建立索引的时间可能不值得。应把准备成本、查询次数和维护成本一起考虑。
records = [{"name": "小林", "score": 90},
{"name": "小周", "score": 80}]
by_name = {row["name"]: row for row in records}
print(by_name["小周"]["score"]) # 80
该例约定姓名唯一；重复姓名会覆盖旧映射，业务规则必须先确定。
8. 一个完整的编程过程
- 明确输入、输出、边界与错误处理。
- 选择数据结构和算法。
- 写出步骤与不变式，再用语言实现。
- 用正常、边界与反例输入检查。
- 分析性能；有必要时再测量实际运行成本。
不必把这些阶段当作只能走一遍的流水线。发现约束变化时，可能要回到前一步。
9. 为什么有现成组件还要学算法？
理解算法，是为了知道组件的前提、成本和失效边界。例如 list.pop(0) 看起来只删除一项，却可能移动很多引用；sorted 很方便，但它不会自动解决输入文件比内存还大的问题。
实际工作可以使用可靠组件；教学实现帮助理解选择依据，不意味着每个项目都要手写快排或哈希表。
10. 终止性、正确性与效率分别检查
循环必须取得进展。遍历列表时，下标走向 n；二分搜索时，候选区间缩小。正确结果但无限循环不能完成任务；能停止但返回错误结果也不算正确。
正确性确认后，再分析操作次数和额外存储。原稿把“算法”和“程序”并列讨论，本教材将二者明确区分，避免把语法熟练等同于算法设计。
11. 手工跟踪与边界测试
assert maximum_indexed([3, 1, 8, 2]) == 8
assert maximum_indexed([-5, -2]) == -2
assert maximum_indexed([7]) == 7
assert maximum_indexed([4, 4]) == 4
try:
maximum_indexed([])
except ValueError:
print("空输入按约定拒绝")
跟踪时记录“已处理范围、当前 best、下一步读哪项”，不要只看最后输出。
12. 本章学习目标
能区分规格、算法和程序；用最大值算法解释循环不变式；说明列表、字典等组织方式如何影响操作成本；为负数、空输入和单项写出检查用例。