干货版《算法导论》 01：从问题定义到正确性证明

✨ 算法导论 01从问题定义到正确性证明 开篇这门课到底在教什么 一、先搞懂什么是「计算问题」1.1 形式化定义 ⚙️1.2 图示二分图模型 1.3 为什么不用枚举 二、什么是「算法」—— 从数学到工程2.1 数学定义 2.2 通俗理解 ️ 三、经典案例生日重复检测算法3.1 问题描述3.2 算法思路自然语言版3.3 流程图示 3.4 伪代码实现 四、硬核用数学归纳法证明正确性4.1 归纳假设Inductive Hypothesis4.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 个人中存在重复则算法在访问第 k1 人之前就已返回 True4.2 证明结构Base Casek00 人无重复假设空洞成立 ✅Inductive Step假设对 kk′ 成立证 k′1 也成立情况 1前 k′ 已有重复 → 由归纳假设已提前返回情况 2前 k′ 无重复若第 k′1 人与前面重复 → 本轮检测到返回 True若不重复 → 加入 seen假设对 k′1 仍成立结论对所有 k ≤ n 成立 → 遍历完 n 人必给出正确答案 ✔️⏱️ 五、效率我们为什么关心快慢效率不只是「跑多快」而是在输入规模无限增长时你的步骤如何增长生日算法最坏 O (n²)顺序查找优化用哈希表 → O (n)这门课的后半程就是教你如何把慢算法变快并用数学证明它最快 六、结语算法的浪漫算法从来不是冰冷的指令堆砌 它是用有限对抗无限用确定消解不确定用逻辑说服所有人下一讲我们将走进时间复杂度、渐近记号与分治法真正开始「把算法玩明白」。 课后小思考把生日算法改成返回第一对重复者伪代码如何写用归纳法证明你的新版算法依然正确需要我把生日算法改成返回第一对重复者的完整伪代码并补充归纳证明吗