3.10 综合练习
这一节的目的是把第三章的核心判断动作合在一起：
- 判断排序算法是否正确
- 分析复杂度
- 选择合适的排序/查找策略
- 审查 agent 输出
提交练习时，不只交答案，还要交你的判断过程。
基本理解
练习 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
以下快排实现有什么问题？
python
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：二分查找边界
以下实现有什么问题？
python
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：输入数据特征，自动选择排序策略。
python
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 连接