第 5 课
复杂度与分治
人工智能程序设计与实践 · 2026 年秋季学期 · 第 6 周 周五 第 1-4 节 · 4 学时连堂
本课口令： ••••••
扫码或访问 aip-2026f.dev-learn-hub.me/a5 → 输入上方口令 → 在自己设备上同步看幻灯片
下课后教师将关闭本课幻灯片，请当堂记好笔记
← 左右滑动翻页 →
里程碑本课为第二章·经典算法基础开篇，教材正式登场，HW1（算法实验报告）当场发布
本节课你将完成什么
1算法与大 O 直觉 — 建立"算法快慢"的量化直觉，能从大 O 读出增长趋势
2分治与合并排序 — 理解分治三步，亲手验证合并排序 + 二分查找
3性能实验 — 用 benchmark 亲眼看见 O(n²) 与 O(n log n) 的差距
4HW1 发布 — 第一次计分作业，11/13 截止，今天领题
你手里的资源
实践指南五《复杂度与分治》
本课随堂操作主线：算法五特征、大 O 表、分治三步、合并排序实现、性能实验。本页幻灯片只讲做什么，怎么做看指南。教材第 1、2 章
算法设计与分析基础（第 1 章）、分治法（第 2 章）。从本课起教材正式登场——算法思想从教材学，代码由 TRAE CODE 写，你负责设计与验证本课幻灯片
扫码进入（口令在投影第一页），下课后关闭，复习请看实践指南评价系统
HW1 登记入口 + 检查点数值校验（排序结果、查找次数、benchmark 倍数关系）本课知识体系
①算法与大 O 直觉 — 五特征 + 大 O 排序 + 最坏/平均
▼
②分治三步与合并排序 — 分解-解决-合并 + 二分查找
▼
③性能实验看见差距 — benchmark：冒泡 vs 合并
▼
④HW1 发布 — 算法实验报告，11/13 截止
定位第二章·经典算法基础开篇——从今天起你正式使用教材。算法思想从教材学，代码由 TRAE CODE 写，你负责设计与验证。下预告：第 6 课贪心 + 动态规划
① 算法的五个特征
教材 1.2
| # | 特征 | 一句话 |
|---|---|---|
| 1 | 输入 | 接受外部提供的数据 |
| 2 | 输出 | 产出至少一个结果 |
| 3 | 确定性 | 每步无歧义 |
| 4 | 有限性 | 有限步内结束 |
| 5 | 可行性 | 能机械执行 |
判断标准
一个有限步内结束、每步无歧义、能机械执行的过程，就是算法。
为什么在意不是所有"代码"都是算法——比如一个死循环就不满足有限性。理解边界，才能在 AI 给你一段"看起来能跑"的代码时，判断它是不是真算法
① 大 O：不看秒数看增长趋势
教材 1.3 渐进时间
| 大 O | 直觉 | n=1000 时操作量级 |
|---|---|---|
| O(1) | 瞬间 | 1 |
| O(log n) | 翻字典 | ~10 |
| O(n) | 数一遍 | 1,000 |
| O(n log n) | 好排序 | ~10,000 |
| O(n²) | 两两比 | 1,000,000 |
金融例子
| 大 O | 场景 |
|---|---|
| O(1) | 查余额 |
| O(log n) | 二分找利率档 |
| O(n) | 遍历客户 |
| O(n log n) | 排序全部交易 |
| O(n²) | 朴素比对所有客户对 |
核心观念n 翻倍时，O(n²) 的代价翻 4 倍，O(n log n) 翻约 2 倍。为什么银行系统对百万级交易必须选 O(n log n) 的算法？性能实验会给你答案
① 最坏 / 平均情况
三种情况
| 情况 | 排序的例子 |
|---|---|
| 最好 | 数组已排好 |
| 最坏 | 数组逆序 |
| 平均 | 随机分布 |
工程习惯
我们说复杂度通常指最坏——给系统设计留安全边际。
银行的批量作业不能假设"运气好"，必须按最坏情况设计容量。
为什么给系统设计留安全边际——这是工程思维。学术研究可以谈平均，工程落地必须谈最坏
② 分治三步
1分解（Divide） — 把大问题切成两半
2解决（Conquer） — 递归解决小问题（小到直接解）
3合并（Combine） — 把两个有序答案拼成一个有序整体
教材 2.1分治不是"递归"的同义词——递归是一种实现手段，分治是一种问题分解思想。看到大问题先问：能不能切两半？
② 合并排序
算法过程
- 数组对半分到单元素（天然有序）
- 两两合并有序对
- 逐层向上合并
复杂度
- T(n) = 2T(n/2) + O(n)
- O(n log n)
- 最坏 = 平均 = 最好（都是 n log n）
教材 2.2合并排序是分治思想的"教科书例子"——分解、解决、合并三步清晰可辨。后面写代码时，要在代码注释里指出哪几行对应哪一步
② 二分查找（分治的亲戚·减治）
前提与过程
- 前提：数组必须有序
- 每次比较砍一半
- O(log n)
金融案例
利率表 1024 档：
- 顺序找最多 1024 次
- 二分最多 10 次
故意实验
传入未排序数组会怎样？
结果不可预测——可能找不到，可能返回错的档位。
亲手触发一次，理解"前提"二字的分量。
关键二分查找的强大依赖一个前提：有序。这个前提不写在 API 里，只写在算法定义里。AI 给你 binary_search 时，你要追问"它假设输入有序了吗"
③ 性能实验·Step 1-2
Step 1 合并排序的实现与验证
指令示范：
text
实现教材第2章的合并排序 merge_sort(nums)：
- 严格按"分解-解决-合并"三段结构写，函数带中文注释
- 再写一个 main：对 [8,3,5,1,9,2] 排序并打印检查点 1：输出 [1, 2, 3, 5, 8, 9]；且代码中能指出哪几行是"分解"、哪几行是"合并"。
Step 2 二分查找
实现 binary_search(rates, target)（rates 有序）；在 1024 档模拟利率表中找 3.75%。
检查点 2：返回正确档位，打印查找次数（应 ≤ 10 次）。
故意实验：传入未排序数组会怎样？结果不可预测——亲手触发一次，理解"前提"二字的分量。
关键检查点不是形式——评价系统会跑你的代码、看输出。AI 一步写对了，你也要能指出"哪几行是分解、哪几行是合并"
③ 性能实验·Step 3 benchmark（本课高潮）
任务
text
写 benchmark.py：
- 生成 n=1000/2000/4000/8000 的随机整数数组各一份
- 分别用"冒泡排序(自己实现)"和"合并排序(Step1的)"计时
- 用 timeit 每档跑3次取均值
- 输出对照表：n、冒泡耗时、合并耗时、倍数关系检查点 3
- n 翻倍时，冒泡耗时 ≈ ×4
- n 翻倍时，合并耗时 ≈ ×2
- n=8000 时合并比冒泡快一个数量级以上
看懂了什么：把表贴进报告——这就是 HW1 的核心素材。
本课高潮这是第一次你亲眼看见大 O 的差距。理论说 n² 比 n log n 快，但只有亲手跑了 benchmark，观念才真正落地
④ HW1 发布：算法实验报告
任务概览
- 名称：算法实验报告
- 截止：11/13（第 9 次课前）
- 提交：自己仓库
hw1/目录 + 评价系统登记 - 组成：
- 实验代码（merge_sort / binary_search / benchmark 三脚本，可复现）
- 实验报告 md
- AI 使用记录
报告内容
- 算法思想复述（自己的话，各 ≤ 5 行）
- 性能数据表 + 增长规律解读
- 二分查找"未排序翻车"实验记录
- 结论：什么规模该换什么算法
- AI 使用记录（关键指令原文 + 验证过程）
详见实践指南五。
第一次计分这是本课第一次计分作业。过程分已由评价系统累计（自学周 + 第 4-5 次课），报告与代码另占一部分。诚实是唯一要求——"我用 AI 一步写对"与"我调试了五轮"都值得写
自主实践任务
案例复现三步全通 + 三个检查点 + 提交规范 + push（详见实践指南）
自主实践①给 merge_sort 加"递归深度打印"，观察 8000 元素的递归树深度（应 ≈ 13，为什么？）②把 benchmark 扩展到 Python 内置
sorted()，对比"轮子 vs 自造" ③用二分查找在真实利率表（自制 100 档）找"月供最接近 5000 的利率" ④AI 使用记录独立研究①教材第 3 章"减治法"与分治的区别一句话 + 拓扑排序是哪种 ②
sys.setrecursionlimit 是干什么的，合并排序 10 万元素会不会撞递归上限（做实验） ③随机数组 vs 逆序数组，合并排序耗时几乎不变——为什么红线
红线 1benchmark 数据必须真实运行产出（评价系统可要求现场复跑）
红线 2报告中的算法思想用自己的话（与教材逐字重合会被查）
红线 3AI 使用记录如实——"我用 AI 一步写对"与"我调试了五轮"都值得写，诚实是唯一要求
S3 思政落点大 O 是工程取舍的标尺——选对算法既省算力又省能耗（绿色计算）。诚实记录 AI 使用过程，是学术诚信在 AI 时代的具体实践
速查表：性能实验常用代码
| 需求 | 代码 |
|---|---|
| 计时 | import timeit; timeit.timeit('f()', globals=globals(), number=3) |
| 生成随机数组 | import random; [random.randint(0,100000) for _ in range(n)] |
| 递归深度 | import sys; sys.getrecursionlimit() |
| 内置排序 | sorted(nums)（Timsort，最坏 O(n log n)） |
| 需求 | 代码 |
|---|---|
| 设置递归上限 | sys.setrecursionlimit(20000) |
| 算n倍数 | import math; math.log2(n) |
| 复制数组避免原地修改 | arr_copy = arr[:] |
| 检查是否有序 | all(arr[i] <= arr[i+1] for i in range(len(arr)-1)) |
小贴士benchmark 时每次用新数组副本——排序是原地操作，跑完一遍数组就变了，第二遍计时不再是同一份数据
求助阶梯
1实践指南五对应部分 — 算法五特征、大 O 表、分治三步、benchmark 模板
2教材第 1、2 章精读 — 算法思想的原典，不懂的概念回教材查
3llm2-isc 概念答疑 — 让 AI 出题考你（"出 5 道大 O 排序题"）
4TRAE CODE 生成代码 — merge_sort / binary_search / benchmark
5举手 — 现场课，教师就在教室
按此顺序前三步能解决 90% 的问题。算法不像 Git 命令——概念有深度，回教材读原文比 AI 二次解释更可靠
资源与下载
学生实践指南五 · docx
算法五特征 + 大 O 表 + 分治三步 + 合并排序实现 + 性能实验 + 红线课堂作业五 · 作业要求 docx
案例复现 + 自主实践 + 独立研究任务详HW1 大作业模板
算法实验报告模板（11/13 截止）本课幻灯片
aip-2026f.dev-learn-hub.me/a5 · 口令随堂公布下课后幻灯片关闭，复习请看实践指南
今天的节奏（4 学时连堂）
第 1-2 学时算法与大 O + 分治与合并排序 — 五特征 + 大 O 表 + 分治三步 + 合并排序演示
课间休息10 分钟
第 3 学时性能实验 Step 1-3 — merge_sort / binary_search / benchmark 三步全跑通，记录检查点
第 4 学时HW1 发布 + 自主实践启动 — 领题、读模板、启动递归深度观察与 sorted() 对比
第二章开篇从今天起教材正式登场——算法思想从教材学，代码由 TRAE CODE 写，你负责设计与验证。下预告：第 6 课贪心 + 动态规划
现在，开始第二章
① 算法与大 O 直觉 — 五特征 + 增长趋势
② 分治与合并排序 — 分解-解决-合并
③ 性能实验看见差距 — benchmark 高潮
④ HW1 发布 — 11/13 截止，今天领题
第二章·经典算法基础实践指南 → 教材 → llm2-isc → TRAE CODE → 举手。下课后幻灯片关闭，复习请看实践指南。下周第 6 课：贪心 + 动态规划