✨ 算法导论 01：从问题定义到正确性证明
- 🔖 开篇：这门课，到底在教什么？
- 🧩 一、先搞懂：什么是「计算问题」？
- 1.1 形式化定义 ⚙️
- 1.2 图示：二分图模型 📊
- 1.3 为什么不用枚举？
- 🚀 二、什么是「算法」？—— 从数学到工程
- 2.1 数学定义 📐
- 2.2 通俗理解 🍽️
- 🎂 三、经典案例：生日重复检测算法
- 3.1 问题描述
- 3.2 算法思路（自然语言版）
- 3.3 流程图示 🔁
- 3.4 伪代码实现 📝
- 🧪 四、硬核：用数学归纳法证明正确性
- 4.1 归纳假设（Inductive Hypothesis）
- 4.2 证明结构
- ⏱️ 五、效率：我们为什么关心快慢？
- 🌌 六、结语：算法的浪漫
- 📌 课后小思考
代码是躯壳，逻辑是灵魂；算法不止是求解，更是证明正确、论证高效、传递思想的艺术 🎯
🔖 开篇：这门课，到底在教什么？
MIT 算法导论第一讲开宗明义：
算法课 ≠ 只教你写代码
它真正的使命是三件事：
Solve computational problems（求解计算问题）
Prove correctness（证明解法正确）
Argue efficiency（论证解法高效）
Communicate ideas（把思想讲给人听懂）
一句话总结：
我们要做的，是用有限步骤，驯服任意规模的输入，给出确定、正确、可解释的答案。
🧩 一、先搞懂：什么是「计算问题」？
1.1 形式化定义 ⚙️
计算问题 = 输入集合 I → 输出集合 O 之间的二元关系
对每个输入 i ∈ I，指定若干合法输出o ∈ O
不要求唯一输出，但必须有明确对错
1.2 图示：二分图模型 📊
[输入空间] [输出空间] i1 ────────→ o1 i2 ─────┬─→ o2 └─→ o3 i3 ────────→ o4边：代表「该输出对该输入合法」
问题：就是这张二分图的结构
1.3 为什么不用枚举？
枚举：对每个输入硬编码答案 → 只适用于小实例
实际：用谓词（Predicate）定义
给定 (i,o)，能机械判断 o 是否合法
例：数组中找值为 5 的下标 → 检查该位置是否等于 5 即可
🚀 二、什么是「算法」？—— 从数学到工程
2.1 数学定义 📐
算法 = 确定函数 f: I → O
满足：
每个输入 →唯一输出
输出必是问题定义的合法解
有限步骤、可机械执行、必终止
2.2 通俗理解 🍽️
算法就是一份菜谱：
原料：输入
步骤：明确指令
成品：正确输出
不管厨房多大、食材多少，按菜谱走，总能做出对的菜。
🎂 三、经典案例：生日重复检测算法
3.1 问题描述
给定 n 个人的生日，判断是否存在两人同一天生日
要求：算法适用于任意 n（教室、全校、Facebook 海量用户）
3.2 算法思路（自然语言版）
维护一个「已见生日」记录集合
按顺序遍历每个人
对当前人：
若生日已在记录中 →返回存在重复
否则 → 加入记录
遍历结束未找到 →返回无重复
3.3 流程图示 🔁
开始 ↓ 初始化空记录集 ↓ 取第 k 个人 ↓ 生日在记录里？──是→ 输出「有重复」 ↓否 加入记录 ↓ 所有人遍历完？──否→ 取下一人 ↓是 输出「无重复」3.4 伪代码实现 📝
Algorithm: CheckBirthdayDuplicate(S) Input: 序列 S = [b₁, b₂, ..., bₙ]，每个 bᵢ 为生日 Output: 是否存在重复，True/False 1. seen ← 空集合 2. for each birthday b in S: 3. if b ∈ seen: 4. return True 5. add b to seen 6. return False🧪 四、硬核：用数学归纳法证明正确性
4.1 归纳假设（Inductive Hypothesis）
若前 k 个人中存在重复，则算法在访问第 k+1 人之前就已返回 True
4.2 证明结构
Base Case（k=0）
0 人无重复，假设空洞成立 ✅Inductive Step
假设对 k=k′ 成立，证 k′+1 也成立：情况 1：前 k′ 已有重复 → 由归纳假设，已提前返回
情况 2：前 k′ 无重复
若第 k′+1 人与前面重复 → 本轮检测到，返回 True
若不重复 → 加入 seen，假设对 k′+1 仍成立
结论
对所有 k ≤ n 成立 → 遍历完 n 人必给出正确答案 ✔️
⏱️ 五、效率：我们为什么关心快慢？
效率不只是「跑多快」，而是：
在输入规模无限增长时，你的步骤如何增长？
生日算法：最坏 O (n²)（顺序查找）
优化：用哈希表 → O (n)
这门课的后半程，就是教你：如何把慢算法变快，并用数学证明它最快
🌌 六、结语：算法的浪漫
算法从来不是冰冷的指令堆砌 🧊
它是：
用有限对抗无限
用确定消解不确定
用逻辑说服所有人
下一讲，我们将走进时间复杂度、渐近记号与分治法，真正开始「把算法玩明白」。
📌 课后小思考
把生日算法改成返回第一对重复者，伪代码如何写？
用归纳法证明：你的新版算法依然正确
需要我把生日算法改成返回第一对重复者的完整伪代码，并补充归纳证明吗？
