简介本资源是麻省理工学院经典课程《算法导论》6.046J/18.401J的权威课堂笔记PDF面向计算机科学专业本科生、算法初学者及自学者系统解决算法概念理解、设计逻辑构建与性能分析能力培养等核心问题。文件共1个PDF大小2.52MB内容完整覆盖课程导论、算法定义与分类、设计步骤与原则、排序算法含插入排序详尽推演、伪代码实现及时间/空间复杂度分析等关键模块附带MIT原课手写风格讲义页眉、典型输入输出示例与分步图解便于对照学习与复习巩固。已有460人学习下载笔记结构清晰、术语规范、例证扎实可作为CLRS教材的高效补充材料帮助读者建立严谨的算法思维框架快速掌握从问题建模到效率评估的完整闭环。1. 这不是一本“速成算法手册”而是 MIT 教你用数学语言给程序做体检的临床笔记如果你正卡在 LeetCode 中等题反复超时、面试被问“为什么快排平均 O(n log n) 而不是 O(n²)”时哑口无言或者写完归并排序却说不清递归树里每层到底做了多少次比较——那你手里的这份《麻省理工学院算法导论笔记.pdf》不是“复习资料”而是一份可执行的算法诊断说明书。它不教你怎么背模板而是从 Day 1 就逼你直面一个事实所有性能问题本质都是对输入规模 n 的函数关系没建模清楚。这份笔记源自 MIT 6.046J 课程首讲实录2001 年秋季由 CLRS 作者之一 Charles E. Leiserson 亲授全文 20 页 PDF没有代码、没有 IDE 截图、甚至没有一张流程图但每一页都在训练你用渐近分析asymptotic analysis这把手术刀切开算法黑匣子精准定位时间/空间消耗的病灶位置。它适合三类人刚写完第一个 for 循环却不知复杂度怎么算的新人刷了 200 道题仍分不清“最坏”和“平均”适用边界的中级选手以及想把“O(n²) 太慢”这种玄学判断转化成可量化、可推导、可优化的技术决策的老手。这不是让你“学算法”而是教你像医生看心电图一样读伪代码——这才是真正能落地的解决方案。2. 从插入排序开始为什么 MIT 用 18 页幻灯片只讲一个 O(n²) 算法2.1 插入排序不是教学摆设而是渐近分析的“原子标尺”MIT 课程用整整 18 页L1.7–L1.24拆解插入排序绝非炫技。它的核心价值在于提供一个足够简单、足够透明、足够可推导的基准模型让你亲手验证“为什么 O(n²) 是上界”。注意这里的关键不是记住公式而是理解推导过程中的每一个假设。比如 L1.19 明确指出“Running time depends on the input”——这意味着你不能脱离具体输入谈性能。当输入已是升序时内层 while 循环一次都不执行实际运行时间是 Θ(n)而当输入是降序时每次 j 迭代都要把已排序部分全部后移总比较次数是 ∑_{j2}^n (j−1) n(n−1)/2即 Θ(n²)。这个推导过程就是你在面试中被追问“最坏情况怎么来的”时唯一能拿出手的硬证据。2.2 伪代码到数学表达手把手把A[i1] ← A[i]翻译成求和式我们来复现笔记 L1.7 的伪代码并严格对应到数学分析def insertion_sort(A): n len(A) for j in range(1, n): # 注意Python 索引从 0 开始j 对应原笔记的 j-1 key A[j] i j - 1 # 下面这个 while 循环的执行次数就是关键 while i 0 and A[i] key: A[i 1] A[i] i - 1 A[i 1] key提示原笔记使用 1-based indexingA[1..n]而 Python 是 0-based。复现时务必注意索引偏移否则推导会错位。这是新手最容易翻车的第一步。现在聚焦while循环对每个 j设 t_j 表示该轮循环执行的次数即比较次数。则总比较次数 T(n) ∑_{j1}^{n−1} t_j。最好情况已升序t_j 1只比一次 A[i] key 就跳出T(n) n−1 Θ(n)最坏情况已降序t_j ji 从 j−1 一路减到 −1T(n) ∑_{j1}^{n−1} j (n−1)n/2 Θ(n²)平均情况需假设输入是随机排列此时 t_j 的期望值为 (j1)/2T(n) ∑_{j1}^{n−1} (j1)/2 ≈ n²/4 Θ(n²)这个推导链条就是笔记 L1.19–L1.20 的全部灵魂。它告诉你O(n²) 不是拍脑袋的结论而是对最坏输入下比较次数求和的结果。没有这个推导你就永远在背结论有了它你才能举一反三分析其他算法。2.3 为什么“Best-case is bogus”—— MIT 教你识别算法分析的陷阱笔记 L1.20 直接打脸“最好情况分析”称其为 “bogus”荒谬的。这不是否定乐观估计而是警告你依赖最好情况做工程决策等于拿彩票中奖概率当系统 SLA。例如有人看到插入排序最好情况是 Θ(n)就认为“小数据快”却忽略现实场景中数据极少完全有序数据库索引重建日志按时间戳插入即使有序现代 CPU 的分支预测失败惩罚可能比多几次比较更致命更重要的是你无法在部署前保证输入永远有序MIT 的潜台词是工程上只认 Worst-case 和 Average-case因为前者给你底线保障后者反映真实负载。这也是为什么后续课程立刻引入归并排序Worst-case Θ(n log n)因为它用确定性上界替代了插入排序的脆弱乐观。3. 算法分析的三大支柱如何把“感觉慢”变成可计算的数学命题3.1 时间复杂度不是代码行数而是输入规模 n 的函数映射笔记 L1.19 强调“Parameterize the running time by the size of the input”。这句话是算法分析的宪法。很多初学者误以为“for 循环嵌套两层就是 O(n²)”但 MIT 指出必须明确 n 是什么。例如对数组排序n 数组长度对图算法n 可能是顶点数 |V|也可能是边数 |E|必须声明对字符串匹配n 是文本长度m 是模式长度复杂度常写作 O(nm)注意笔记中所有分析都默认 n 为输入序列长度。当你看到 “T(n) maximum time on any input of size n”这里的 n 就是那个被参数化的变量。漏掉这一步所有复杂度讨论都是空中楼阁。3.2 渐近记号的物理意义O、Ω、Θ 不是精度等级而是安全边界MIT 在 L1.19 提到 “seek upper bounds because everybody likes a guarantee”这直指 O 记号的本质O(g(n)) 是一个集合包含所有最终不超过 c·g(n) 的函数。它不承诺“刚好等于”而是承诺“绝不超支”。例如插入排序最坏情况 T(n) n(n−1)/2 ≤ n² ⇒ T(n) ∈ O(n²)但 T(n) 同样 ∈ O(n³)、O(2ⁿ)只是 O(n²) 是紧确上界tight bound而 Θ 记号要求同时满足上界和下界T(n) ∈ Θ(n²) 当且仅当 ∃c₁,c₂,n₀ 使得 ∀nn₀, c₁n² ≤ T(n) ≤ c₂n²。这就是为什么 MIT 说插入排序最坏是 Θ(n²) —— 它既不会比 n² 慢太多也不会比 n² 快太多。3.3 为什么“Correctness”排在“Performance”之前—— 算法设计的底层逻辑笔记 L1.4 列出比性能更重要的 10 项modularity、correctness、maintainability… 这不是客套话。MIT 用排序问题示范了这个优先级Correctness正确性输出必须是输入的排列且满足 a₁ ≤ a₂ ≤ … ≤ aₙL1.6Robustness鲁棒性算法必须处理空数组、单元素、重复元素笔记虽未明说但伪代码i 0已隐含边界保护Simplicity简洁性插入排序只有 6 行核心逻辑易验证、易调试血泪经验我曾见过团队为追求 O(n log n) 强上红黑树排序结果因边界条件处理错误导致线上订单乱序。后来回退到插入排序数据量 50加一行assert sorted(A) sorted(A, keylambda x: x.id)故障率归零。性能优化永远在正确性之后这是工程师的底线。4. 避坑从 MIT 笔记里挖出的 4 个真实踩坑点全是面试高频雷区4.1 现象面试官问“插入排序空间复杂度”答“O(1)”被追问“为什么不是 O(n)”原因混淆了“额外空间”和“总空间”。插入排序原地操作只用常数个变量key, i, j所以额外空间是 O(1)。但若把输入数组 A 的存储也算进去总空间是 Θ(n)。算法分析中Space Complexity 默认指额外空间auxiliary space这是 CLRS 和 MIT 的约定俗成。答“O(n)”说明没吃透定义。解决永远明确回答“额外空间复杂度为 O(1)因为除输入数组外只使用了固定数量的变量。”4.2 现象用 Python 实现插入排序测试 [5,2,4,6,1,3] 输出错序debug 半小时原因Python 列表索引与笔记 1-based indexing 错位。笔记中A[1..n]Python 是A[0..n-1]。常见错误写法# ❌ 错误j 从 0 开始但 i j-1 会越界 for j in range(0, n): key A[j] i j - 1 # j0 时 i-1A[-1] 取末尾元素解决严格对齐笔记逻辑j 从 1 开始对应 Python 索引 1# ✅ 正确j 从 1 到 n-1Python 索引 for j in range(1, n): key A[j] i j - 1 while i 0 and A[i] key: # 注意 i 0 A[i 1] A[i] i - 1 A[i 1] key4.3 现象声称“平均情况 O(n²) 比最坏情况实用”被质疑“那为什么不用快排”原因误解“平均”的前提。插入排序平均 O(n²) 成立的条件是输入是随机排列uniform random permutation。但现实数据往往有局部有序性如时间序列、ID 递增此时插入排序实际性能接近 Θ(n)而快排可能因 pivot 选择不当退化到 Θ(n²)。说“平均 O(n²) 更实用”是偷换概念——实用与否取决于你的数据分布而非理论平均值。解决回答时必须绑定前提“在随机排列假设下插入排序平均比较次数为 n²/4但若数据基本有序其实际性能可达 Θ(n)此时优于通用 O(n log n) 算法。”4.4 现象写复杂度时混用 O 和 Θ如“插入排序是 O(n²)”被指出“不严谨”原因O 是上界Θ 是紧确界。插入排序最坏情况既是 O(n²) 也是 Ω(n²)所以是 Θ(n²)。但若只说 O(n²)技术上没错因为 Θ(n²) ⊂ O(n²)却丢失了“它不可能更快”的关键信息。MIT 笔记 L1.19 明确用 “T(n) maximum time” 定义 worst-case这天然导向 Θ 记号。解决对确定性上界/下界优先用 Θ对仅知上界如某些启发式算法才用 O。面试中可补充“最坏情况是 Θ(n²)意味着它既不会比 n² 慢太多也不会比 n² 快太多。”5. 把 MIT 笔记变成你的算法“CT 扫描仪”用三步法诊断任意算法5.1 第一步锁定输入规模 n并写出最坏输入的构造方法不要跳过这一步很多算法分析失败源于 n 定义模糊。以快速排序为例n 数组长度标准定义最坏输入构造每次选最小/最大元素作 pivot如已排序数组 选首元素为 pivot验证递归树退化为链状深度 n每层 partition 比较 n−1, n−2,…,1 次总和 Θ(n²)这个构造过程就是你在白板上向面试官证明“为什么快排会退化”的核心证据。MIT 笔记虽只讲插入排序但其方法论——先定义 n再构造极端输入再数学求和——可直接迁移。5.2 第二步画出“操作计数树”把伪代码翻译成数学求和式别信直觉动手算。以归并排序MIT 后续课重点为例其递归式 T(n) 2T(n/2) Θ(n)。MIT 教你用递归树展开根层Θ(n) 次合并操作第二层2 个子问题各 Θ(n/2)共 Θ(n)第三层4 个子问题各 Θ(n/4)共 Θ(n)…共 log₂n 层每层 Θ(n)总 T(n) Θ(n log n)这个树就是你对抗“感觉慢”的武器。当你面对新算法立刻画树节点标操作类型比较/移动/递归调用边标子问题规模层标总代价。树画出来求和式自然浮现。5.3 第三步用“反例证伪法”检验你的复杂度结论MIT 的严谨性体现在任何结论都必须能被反例推翻。例如若你声称“某算法最坏 O(n)”那就必须证明不存在任何输入使比较次数超过 c·n。反之若你找到一个输入序列使比较次数达到 n²/2则 O(n) 结论立即破产。我在带新人时强制他们做这件事给出复杂度结论写出对应的反例构造规则如“对插入排序降序数组即最坏输入”用该规则生成一个具体小例子如 [5,4,3,2,1]手动模拟并计数从那以后我每次分析新算法都强制走一遍“定义 n → 构造最坏输入 → 手动小例验证 → 求和推导”四步闭环。哪怕只花 3 分钟也比凭感觉写 O(n²) 强十倍。这份 MIT 笔记最珍贵的不是它讲了什么而是它教会你算法性能不是玄学是可测量、可证伪、可推导的工程事实。希望帮到你。本文还有配套的精品资源点击获取
MIT算法导论笔记：用渐近分析给程序做性能体检
简介本资源是麻省理工学院经典课程《算法导论》6.046J/18.401J的权威课堂笔记PDF面向计算机科学专业本科生、算法初学者及自学者系统解决算法概念理解、设计逻辑构建与性能分析能力培养等核心问题。文件共1个PDF大小2.52MB内容完整覆盖课程导论、算法定义与分类、设计步骤与原则、排序算法含插入排序详尽推演、伪代码实现及时间/空间复杂度分析等关键模块附带MIT原课手写风格讲义页眉、典型输入输出示例与分步图解便于对照学习与复习巩固。已有460人学习下载笔记结构清晰、术语规范、例证扎实可作为CLRS教材的高效补充材料帮助读者建立严谨的算法思维框架快速掌握从问题建模到效率评估的完整闭环。1. 这不是一本“速成算法手册”而是 MIT 教你用数学语言给程序做体检的临床笔记如果你正卡在 LeetCode 中等题反复超时、面试被问“为什么快排平均 O(n log n) 而不是 O(n²)”时哑口无言或者写完归并排序却说不清递归树里每层到底做了多少次比较——那你手里的这份《麻省理工学院算法导论笔记.pdf》不是“复习资料”而是一份可执行的算法诊断说明书。它不教你怎么背模板而是从 Day 1 就逼你直面一个事实所有性能问题本质都是对输入规模 n 的函数关系没建模清楚。这份笔记源自 MIT 6.046J 课程首讲实录2001 年秋季由 CLRS 作者之一 Charles E. Leiserson 亲授全文 20 页 PDF没有代码、没有 IDE 截图、甚至没有一张流程图但每一页都在训练你用渐近分析asymptotic analysis这把手术刀切开算法黑匣子精准定位时间/空间消耗的病灶位置。它适合三类人刚写完第一个 for 循环却不知复杂度怎么算的新人刷了 200 道题仍分不清“最坏”和“平均”适用边界的中级选手以及想把“O(n²) 太慢”这种玄学判断转化成可量化、可推导、可优化的技术决策的老手。这不是让你“学算法”而是教你像医生看心电图一样读伪代码——这才是真正能落地的解决方案。2. 从插入排序开始为什么 MIT 用 18 页幻灯片只讲一个 O(n²) 算法2.1 插入排序不是教学摆设而是渐近分析的“原子标尺”MIT 课程用整整 18 页L1.7–L1.24拆解插入排序绝非炫技。它的核心价值在于提供一个足够简单、足够透明、足够可推导的基准模型让你亲手验证“为什么 O(n²) 是上界”。注意这里的关键不是记住公式而是理解推导过程中的每一个假设。比如 L1.19 明确指出“Running time depends on the input”——这意味着你不能脱离具体输入谈性能。当输入已是升序时内层 while 循环一次都不执行实际运行时间是 Θ(n)而当输入是降序时每次 j 迭代都要把已排序部分全部后移总比较次数是 ∑_{j2}^n (j−1) n(n−1)/2即 Θ(n²)。这个推导过程就是你在面试中被追问“最坏情况怎么来的”时唯一能拿出手的硬证据。2.2 伪代码到数学表达手把手把A[i1] ← A[i]翻译成求和式我们来复现笔记 L1.7 的伪代码并严格对应到数学分析def insertion_sort(A): n len(A) for j in range(1, n): # 注意Python 索引从 0 开始j 对应原笔记的 j-1 key A[j] i j - 1 # 下面这个 while 循环的执行次数就是关键 while i 0 and A[i] key: A[i 1] A[i] i - 1 A[i 1] key提示原笔记使用 1-based indexingA[1..n]而 Python 是 0-based。复现时务必注意索引偏移否则推导会错位。这是新手最容易翻车的第一步。现在聚焦while循环对每个 j设 t_j 表示该轮循环执行的次数即比较次数。则总比较次数 T(n) ∑_{j1}^{n−1} t_j。最好情况已升序t_j 1只比一次 A[i] key 就跳出T(n) n−1 Θ(n)最坏情况已降序t_j ji 从 j−1 一路减到 −1T(n) ∑_{j1}^{n−1} j (n−1)n/2 Θ(n²)平均情况需假设输入是随机排列此时 t_j 的期望值为 (j1)/2T(n) ∑_{j1}^{n−1} (j1)/2 ≈ n²/4 Θ(n²)这个推导链条就是笔记 L1.19–L1.20 的全部灵魂。它告诉你O(n²) 不是拍脑袋的结论而是对最坏输入下比较次数求和的结果。没有这个推导你就永远在背结论有了它你才能举一反三分析其他算法。2.3 为什么“Best-case is bogus”—— MIT 教你识别算法分析的陷阱笔记 L1.20 直接打脸“最好情况分析”称其为 “bogus”荒谬的。这不是否定乐观估计而是警告你依赖最好情况做工程决策等于拿彩票中奖概率当系统 SLA。例如有人看到插入排序最好情况是 Θ(n)就认为“小数据快”却忽略现实场景中数据极少完全有序数据库索引重建日志按时间戳插入即使有序现代 CPU 的分支预测失败惩罚可能比多几次比较更致命更重要的是你无法在部署前保证输入永远有序MIT 的潜台词是工程上只认 Worst-case 和 Average-case因为前者给你底线保障后者反映真实负载。这也是为什么后续课程立刻引入归并排序Worst-case Θ(n log n)因为它用确定性上界替代了插入排序的脆弱乐观。3. 算法分析的三大支柱如何把“感觉慢”变成可计算的数学命题3.1 时间复杂度不是代码行数而是输入规模 n 的函数映射笔记 L1.19 强调“Parameterize the running time by the size of the input”。这句话是算法分析的宪法。很多初学者误以为“for 循环嵌套两层就是 O(n²)”但 MIT 指出必须明确 n 是什么。例如对数组排序n 数组长度对图算法n 可能是顶点数 |V|也可能是边数 |E|必须声明对字符串匹配n 是文本长度m 是模式长度复杂度常写作 O(nm)注意笔记中所有分析都默认 n 为输入序列长度。当你看到 “T(n) maximum time on any input of size n”这里的 n 就是那个被参数化的变量。漏掉这一步所有复杂度讨论都是空中楼阁。3.2 渐近记号的物理意义O、Ω、Θ 不是精度等级而是安全边界MIT 在 L1.19 提到 “seek upper bounds because everybody likes a guarantee”这直指 O 记号的本质O(g(n)) 是一个集合包含所有最终不超过 c·g(n) 的函数。它不承诺“刚好等于”而是承诺“绝不超支”。例如插入排序最坏情况 T(n) n(n−1)/2 ≤ n² ⇒ T(n) ∈ O(n²)但 T(n) 同样 ∈ O(n³)、O(2ⁿ)只是 O(n²) 是紧确上界tight bound而 Θ 记号要求同时满足上界和下界T(n) ∈ Θ(n²) 当且仅当 ∃c₁,c₂,n₀ 使得 ∀nn₀, c₁n² ≤ T(n) ≤ c₂n²。这就是为什么 MIT 说插入排序最坏是 Θ(n²) —— 它既不会比 n² 慢太多也不会比 n² 快太多。3.3 为什么“Correctness”排在“Performance”之前—— 算法设计的底层逻辑笔记 L1.4 列出比性能更重要的 10 项modularity、correctness、maintainability… 这不是客套话。MIT 用排序问题示范了这个优先级Correctness正确性输出必须是输入的排列且满足 a₁ ≤ a₂ ≤ … ≤ aₙL1.6Robustness鲁棒性算法必须处理空数组、单元素、重复元素笔记虽未明说但伪代码i 0已隐含边界保护Simplicity简洁性插入排序只有 6 行核心逻辑易验证、易调试血泪经验我曾见过团队为追求 O(n log n) 强上红黑树排序结果因边界条件处理错误导致线上订单乱序。后来回退到插入排序数据量 50加一行assert sorted(A) sorted(A, keylambda x: x.id)故障率归零。性能优化永远在正确性之后这是工程师的底线。4. 避坑从 MIT 笔记里挖出的 4 个真实踩坑点全是面试高频雷区4.1 现象面试官问“插入排序空间复杂度”答“O(1)”被追问“为什么不是 O(n)”原因混淆了“额外空间”和“总空间”。插入排序原地操作只用常数个变量key, i, j所以额外空间是 O(1)。但若把输入数组 A 的存储也算进去总空间是 Θ(n)。算法分析中Space Complexity 默认指额外空间auxiliary space这是 CLRS 和 MIT 的约定俗成。答“O(n)”说明没吃透定义。解决永远明确回答“额外空间复杂度为 O(1)因为除输入数组外只使用了固定数量的变量。”4.2 现象用 Python 实现插入排序测试 [5,2,4,6,1,3] 输出错序debug 半小时原因Python 列表索引与笔记 1-based indexing 错位。笔记中A[1..n]Python 是A[0..n-1]。常见错误写法# ❌ 错误j 从 0 开始但 i j-1 会越界 for j in range(0, n): key A[j] i j - 1 # j0 时 i-1A[-1] 取末尾元素解决严格对齐笔记逻辑j 从 1 开始对应 Python 索引 1# ✅ 正确j 从 1 到 n-1Python 索引 for j in range(1, n): key A[j] i j - 1 while i 0 and A[i] key: # 注意 i 0 A[i 1] A[i] i - 1 A[i 1] key4.3 现象声称“平均情况 O(n²) 比最坏情况实用”被质疑“那为什么不用快排”原因误解“平均”的前提。插入排序平均 O(n²) 成立的条件是输入是随机排列uniform random permutation。但现实数据往往有局部有序性如时间序列、ID 递增此时插入排序实际性能接近 Θ(n)而快排可能因 pivot 选择不当退化到 Θ(n²)。说“平均 O(n²) 更实用”是偷换概念——实用与否取决于你的数据分布而非理论平均值。解决回答时必须绑定前提“在随机排列假设下插入排序平均比较次数为 n²/4但若数据基本有序其实际性能可达 Θ(n)此时优于通用 O(n log n) 算法。”4.4 现象写复杂度时混用 O 和 Θ如“插入排序是 O(n²)”被指出“不严谨”原因O 是上界Θ 是紧确界。插入排序最坏情况既是 O(n²) 也是 Ω(n²)所以是 Θ(n²)。但若只说 O(n²)技术上没错因为 Θ(n²) ⊂ O(n²)却丢失了“它不可能更快”的关键信息。MIT 笔记 L1.19 明确用 “T(n) maximum time” 定义 worst-case这天然导向 Θ 记号。解决对确定性上界/下界优先用 Θ对仅知上界如某些启发式算法才用 O。面试中可补充“最坏情况是 Θ(n²)意味着它既不会比 n² 慢太多也不会比 n² 快太多。”5. 把 MIT 笔记变成你的算法“CT 扫描仪”用三步法诊断任意算法5.1 第一步锁定输入规模 n并写出最坏输入的构造方法不要跳过这一步很多算法分析失败源于 n 定义模糊。以快速排序为例n 数组长度标准定义最坏输入构造每次选最小/最大元素作 pivot如已排序数组 选首元素为 pivot验证递归树退化为链状深度 n每层 partition 比较 n−1, n−2,…,1 次总和 Θ(n²)这个构造过程就是你在白板上向面试官证明“为什么快排会退化”的核心证据。MIT 笔记虽只讲插入排序但其方法论——先定义 n再构造极端输入再数学求和——可直接迁移。5.2 第二步画出“操作计数树”把伪代码翻译成数学求和式别信直觉动手算。以归并排序MIT 后续课重点为例其递归式 T(n) 2T(n/2) Θ(n)。MIT 教你用递归树展开根层Θ(n) 次合并操作第二层2 个子问题各 Θ(n/2)共 Θ(n)第三层4 个子问题各 Θ(n/4)共 Θ(n)…共 log₂n 层每层 Θ(n)总 T(n) Θ(n log n)这个树就是你对抗“感觉慢”的武器。当你面对新算法立刻画树节点标操作类型比较/移动/递归调用边标子问题规模层标总代价。树画出来求和式自然浮现。5.3 第三步用“反例证伪法”检验你的复杂度结论MIT 的严谨性体现在任何结论都必须能被反例推翻。例如若你声称“某算法最坏 O(n)”那就必须证明不存在任何输入使比较次数超过 c·n。反之若你找到一个输入序列使比较次数达到 n²/2则 O(n) 结论立即破产。我在带新人时强制他们做这件事给出复杂度结论写出对应的反例构造规则如“对插入排序降序数组即最坏输入”用该规则生成一个具体小例子如 [5,4,3,2,1]手动模拟并计数从那以后我每次分析新算法都强制走一遍“定义 n → 构造最坏输入 → 手动小例验证 → 求和推导”四步闭环。哪怕只花 3 分钟也比凭感觉写 O(n²) 强十倍。这份 MIT 笔记最珍贵的不是它讲了什么而是它教会你算法性能不是玄学是可测量、可证伪、可推导的工程事实。希望帮到你。本文还有配套的精品资源点击获取