3.10 综合练习
这一节，你能解决什么问题
学完这一节，你能够：
- 综合运用第三章的核心判断方法：循环不变式、复杂度分析、策略选择
- 审查 agent 给出的排序/查找实现，发现边界条件错误和隐藏性能问题
- 设计场景化的算法选择策略，而不是机械地记忆"哪个算法更好"
- 验证算法正确性，不只是"跑一遍看看"
问题情境
你刚学完第三章：排序与查找。
你掌握了：
- 循环不变式证明正确性
- 复杂度分析（最好、最坏、平均）
- 各种排序算法的特点（插入、归并、快排、堆排序、计数排序、基数排序）
- 二分查找及其边界条件
问题：这些知识怎么变成实际判断能力？
让我们通过练习把零散知识变成系统思维。
直观思路
练习的目的是让你"自己做一遍"：
- 基本理解：复现关键概念
- 方法应用：把方法用到新场景
- 错误诊断：发现别人（或 agent）的错误
- 方案比较：权衡取舍
- 开放设计：设计自己的解决方案
这种"主动提取"比"被动阅读"更有效。研究表明，回忆和应用的记忆留存率远高于单纯阅读。
规范定义
第三章的核心判断动作
- 正确性判断：用循环不变式证明，不靠"跑一遍看看"
- 复杂度判断：分析最好、最坏、期望情况
- 策略选择判断：根据场景特征选择算法
- 边界判断：发现边界条件错误
- 前提判断：验证算法前提条件是否满足
练习类型分类
| 类型 | 目的 | 认知层次 |
|---|---|---|
| 基本理解 | 复现概念 | 记忆、理解 |
| 方法应用 | 迁移方法 | 应用 |
| 错误诊断 | 发现问题 | 分析 |
| 方案比较 | 权衡取舍 | 评价 |
| 开放设计 | 综合创造 | 创造 |
这个方法是怎么想到的
为什么要有综合练习？
分散的知识点是孤岛。综合练习是桥梁。
类比：学开车，不能只懂每个操作（油门、刹车、转向），还要能在真实路况中综合运用。
第三章的每个知识点：
- 循环不变式 → 正确性证明
- 复杂度分析 → 性能预测
- 排序算法特点 → 策略选择
综合练习让你在场景中调用这些知识点。
练习的设计原则
- 渐进难度：从基本理解到开放设计
- 场景真实：不考"定义是什么"，而是"这个场景怎么做"
- 过程重于答案：提交判断过程，不只是答案
正确性分析
练习答案的验证方法
练习题的答案不只是"对/错"，而是"推理是否正确"。
例子：排序策略选择
错误答案：
"应该用快排，因为快排最快。"
正确推理：
"应该用堆排序。因为场景要求最坏 Θ(n log n)，快排的最坏是 Θ(n²)。虽然快排期望 Θ(n log n)，但实时系统不能接受最坏情况。堆排序保证了最坏 Θ(n log n)，符合需求。"
验证标准：
- 是否识别了场景约束？
- 是否匹配了算法特点？
- 是否考虑了边界情况？
复杂度分析
练习的时间分配建议
| 练习类型 | 建议时间 | 重点 |
|---|---|---|
| 基本理解 | 每题 5-10 分钟 | 快速复现 |
| 方法应用 | 每题 15-20 分钟 | 迁移思考 |
| 错误诊断 | 每题 10-15 分钟 | 细心审查 |
| 方案比较 | 每题 20-30 分钟 | 权衡分析 |
| 开放设计 | 每题 30-60 分钟 | 综合设计 |
练习的心理陷阱
- 过早求答案：先尝试，再对答案
- 跳过推导：推导过程比结论重要
- 只做简单题：困难题才是提升点
什么时候不该用这个方法
练习不是目的，理解才是
不要：
- 背答案
- 跳过思考
- 只做自己会的
应该：
- 先尝试，再看提示
- 写推理过程
- 从错误中学习
练习之外的补充
练习覆盖了典型场景，但不是全部。实际工作中：
- 实际测量：复杂度分析是理论，实际要测量
- 混合策略：可能需要组合多种算法
- 工程约束：内存、并行、分布式可能改变选择
本节小结
解决了什么问题？
把第三章的零散知识点整合成判断能力。
核心方法是什么？
- 基本理解：复现概念
- 方法应用：迁移到新场景
- 错误诊断：发现问题
- 方案比较：权衡取舍
- 开放设计：综合创造
为什么正确？
主动提取比被动阅读记忆更持久。场景化练习让知识变成能力。
适用场景？
学习第三章后，检验理解程度。发现薄弱环节。
能否自己使用？
能。关键是：
- 不要跳过思考
- 写推理过程
- 从错误中学习
基本理解
练习 1：排序下界验证
用决策树模型证明：排序 3 个元素，最坏情况至少需要 5 次比较。
提示：
- 3! = 6 种排列
- 高度 h 的二叉树最多 2^h 个叶子
- 为什么不是 3 次？
练习 2：循环不变式证明
用循环不变式证明 PARTITION 的正确性：
每次迭代开始时：
- A[p..i] ≤ pivot
- A[i+1..j-1] > pivot
- A[r] 是 pivot
写出完整的三步证明。
练习 3：建堆过程
对数组 [3, 1, 4, 1, 5, 9, 2, 6]，手动执行 BUILD-MAX-HEAP。
画出每一步的树形结构。
方法应用
练习 4：排序策略选择
给定以下场景，选择排序算法并说明理由：
| 场景 | 推荐算法 | 理由 |
|---|---|---|
| 年龄排序（0-150岁），n=10^6 | ||
| URL 排序（字符串），需要稳定 | ||
| 嵌入式系统，内存 2KB，不能崩溃 | ||
| 数据流中位数计算 | ||
| Top-50（n=10^6） |
练习 5：哈希策略分析
缓存系统设计：
- 1000 万条 URL
- 每秒 10 万次查询
- 内存 100 MB
- 假阳性可接受，假阴性不可接受
选择哈希策略，说明理由。
错误诊断
练习 6：快排 bug
以下快排实现有什么问题？
def quicksort_bug(A, p, r):
if p < r:
q = partition(A, p, r)
quicksort_bug(A, p, q) # ← 这里
quicksort_bug(A, q+1, r)分析：递归范围是否正确？
练习 7：计数排序前提
agent 建议用计数排序优化时间戳排序。这个建议正确吗？
分析：
- 时间戳范围
- 数据规模 n
- 是否满足前提条件
练习 8：二分查找边界
以下实现有什么问题？
def binary_bug(A, x):
low, high = 0, len(A) - 1
while low < high: # ← 检查这里
mid = (low + high) // 2 # ← 检查这里
if A[mid] == x:
return mid
elif A[mid] < x:
low = mid # ← 检查这里
else:
high = mid # ← 检查这里
return -1找出所有 bug。
方案比较
练习 9：排序三元悖
不存在同时满足三者的排序算法：
- O(n) 时间
- 稳定
- 原地
验证：列出常见排序算法的（时间、稳定、原地）三元组。
练习 10：三种 Θ(n log n) 排序对比
| 维度 | 归并排序 | 快排 | 堆排序 |
|---|---|---|---|
| 最坏时间 | |||
| 期望时间 | |||
| 空间 | |||
| 稳定 | |||
| 缓存友好 |
填完后，给出场景匹配建议。
开放设计
练习 11：排序策略 Skill
设计一个 Skill：输入数据特征，自动选择排序策略。
def choose_sort_strategy(n, key_type, key_range, stable, worst_required):
# 返回推荐算法和理由测试用例：
- n=100万，整数年龄（0-150），不需要稳定
- n=1万，浮点得分，需要稳定
- n=10亿，字符串 URL，需要最坏保证
练习 12：中位数流 Skill
设计一个 Skill：实时计算数据流中位数。
- 支持动态插入
- 支持快速查询中位数
- 分析复杂度
提示：两个堆（最大堆 + 最小堆）。
审查报告
练习 13：agent 输出审查
让 agent 实现一个排序系统，你审查：
- 是否正确选择策略？
- 循环不变式是否正确？
- 边界条件是否处理？
- 复杂度分析是否准确？
- 前提条件是否验证？
写一份审查报告。
上一节：3.9 二分查找
下一节：3.11 LLM 连接