MIT算法导论第一讲：插入排序与时间复杂度推导实战

简介这份PDF笔记整理自麻省理工学院《算法导论》课程面向计算机专业学生、算法初学者及准备技术面试的开发者系统梳理算法基础、设计原则与性能分析方法。内容涵盖算法的定义与重要性、算法设计需经过问题定义、算法设计、分析与实现等步骤以及常见排序算法分类并以插入排序为例给出完整伪代码、逐步执行示例及O(n²)时间复杂度和O(1)空间复杂度分析帮助读者理解从问题建模到复杂度评估的完整思路。笔记还总结了算法分析的意义与方法包括时间复杂度、空间复杂度等核心指标便于建立算法性能评估的框架。资源为单份PDF文件大小2.52MB便于离线阅读与打印已有460人下载学习。笔记提炼了课程讲稿中的关键知识点与示例适合预习、复习及备考算法相关课程时快速查阅也可作为自学算法的入门参考。1. 麻省理工学院算法导论笔记第一讲为什么先谈“性能”不谈 hello world麻省理工学院的 6.046J/18.401J 算法导论课第一讲给出的排序例子非常简单——8 2 4 9 3 6 排成 2 3 4 6 8 9但它在开课第一天就把一个反直觉的结论拍在桌上正确性、模块化、可维护性都比性能更重要可算法导论整门课研究的恰恰是性能。这份 Fall 2001 的 Lecture 1 笔记适合两类人一类是想系统补算法底子的自学者想弄清“时间复杂度”到底是怎么从一行行伪代码里长出来的另一类是写业务代码两三年、能解决线上问题但面对“这个算法为什么快”说不出一二三的工程师。它不教你调包教的是你如何自己推导出一个算法的运行时间。2. 算法分析的本质可扩展性、可行性边界和“上界保证”2.1 为什么算法课不在第一天教排序而在教“怎么分析排序”课程一开始就把“分析算法”定义成“对计算机程序性能和资源使用的理论研究”。这句话听起来像废话但它是整门课的主线。讲师在第一讲里列出一串“比性能更重要”的属性模块化、正确性、可维护性、功能性、健壮性、用户友好性、程序员时间、简单性、可扩展性、可靠性。如果做的是产品工程这个列表几乎可以当成职业信条抄下来。那为什么还要专门学算法和性能讲义给出了四个理由。第一算法帮助我们理解可扩展性——输入规模变大时程序开销跟不跟得上第二性能往往是可行性与不可行性的分界线同一件事换一种算法就能从“不能做”变成“能做”第三算法数学提供了一种谈论程序行为的通用语言让两个人不必对着同一个接口“玄学调优”第四性能分析的结论可以推广到其他计算资源比如内存、带宽和磁盘 IO。我体会最深的是第二条。曾经接手一个数据量几十万行的报表接口原始实现用双层循环做关联数据量小的时候风平浪静一上生产就十几分钟不出结果。后来换成一个线性扫描加哈希索引的写法耗时从几百秒降到几百毫秒。区别不在于代码写得“漂亮”而在于一个算法把问题从不可能变成了可能。这就是性能作为分界线的含义。2.2 可扩展性为什么 10 倍输入量是算法的试金石“可扩展性”这个词在工程里经常被滥用但讲义里的意思很朴素输入量变成原来的十倍你的程序还能不能活着。插入排序随输入规模呈现二次增长而归并排序接近线性对数增长。n 从 1000 涨到 10000前者时间膨胀约 100 倍后者只涨十几倍。这个差距足够决定一个服务要不要扩容、一批数据要不要分成小块跑。我在实际工作中看到过很多“能跑但不敢加数据”的系统。它们往往不是架构问题而是某个核心步骤用了平方级算法。瓶颈点一旦找到替换成对数级或线性级的做法系统立刻就能扛住下一个数量级。这也是为什么看算法导论不能只停留在“看懂证明”要把可扩展性当成一把尺子随时丈量自己写的关键代码。2.3 为什么我们追寻运行时间的“上界”而不是平均值或直觉第一讲里有个容易被忽略的表述我们一般寻找运行时间的上界因为大家都喜欢一个保证。上界的含义是无论输入是什么算法最多花这么多时间。这和做预算的心态一致——宁可把最坏情况估计清楚也不要被某个特殊输入打爆。做在线服务的人对这个最敏感。p99 响应时间本质就是一种统计意义上的上界承诺绝大多数请求要在多少毫秒内返回。算法分析里的“上界”更严格一些它背靠着输入规模 n 的函数关系可以推导、可以证明。我习惯把一个算法的上界当成它的“债务上限”不去碰它不代表它不存在一旦输入形态变化最坏情况就会找上门。2.4 算法设计的四步流程与这门课的地图把摘要里归纳的算法流程套到这一讲上你会发现整节课的结构其实很清晰先定义问题再设计算法然后分析算法最后才是实现。插入排序只是用来演示这条链路的最小例子。定义问题是把输入输出说清楚设计算法是写出伪代码分析算法是计算运行时间随 n 怎么增长实现则是把它翻译成具体语言。课程大纲也暗示了后续地图排序之后会有搜索算法、图算法、动态规划等。这一讲之所以从排序入手是因为排序问题足够简单形式化定义不费劲又能把复杂度分析的三个维度——最坏、平均、最好——全部演示一遍。看这份笔记时我建议你先别急着往后翻把第一讲吃透比浏览十讲都有用。3. 排序问题的形式化与插入排序从数学定义到可运行代码3.1 先用数学语言定义排序再写代码讲义里对排序问题的定义是输入一个数字序列 〈a1, a2, …, an〉输出一个排列 〈a1, a2, …, an〉使得 a1 ≤ a2 ≤ … ≤ an。注意“排列”这个词输出的元素必须和输入一一对应不能丢掉元素也不能凭空多出元素。这个约束看起来平凡但很多人实现排序时交换逻辑写错本质就是没有守住“排列”这个定义。形式化定义的价值在于为复杂度分析铺路。没有明确的输入规模和输出约束你根本没法说“这个算法对规模为 n 的输入要花多少时间”。我后来写算法笔记都强迫自己先写输入输出定义再写算法步骤。这个习惯就是从这一讲学来的先定义边界再谈实现。3.2 插入排序伪代码逐行拆解插入排序的思路很朴素把数组看成两部分左边是已排序区右边是未排序区每次从右边取一个元素插到左边正确的位置。讲义里的伪代码是这样INSERTION-SORT (A, n) // A[1 . . n] for j ← 2 to n do key ← A[j] i ← j – 1 while i 0 and A[i] key do A[i1] ← A[i] i ← i – 1 A[i1] key逐行解释一下。外层循环从 2 跑到 n意味着默认 A[1] 单个元素天然有序。key 保存当前要插入的元素i 指向已排序区的末尾从后往前扫描。while 条件里的 i 0 是防止越界A[i] key 表示还没找到正确位置于是把 A[i] 整体后移一位给 key 腾位置。循环结束后i 停留在第一个不大于 key 的位置或者停在 0所以 key 被放回 A[i1]。这里最关键的变量是 i 和 key。初学时容易陷入的思维误区是以为已排序区是 A[1..j]实际上 j 指向的是 key 所在的位置已排序区是 j 之前的 A[1..j-1]。这个区分直接决定了循环边界怎么写。3.3 手工模拟8 2 4 9 3 6 的完整过程讲义用一组示例数据演示了插入排序的每一步。我把它整理成一张过程表数组索引按伪代码的 1-based 来写轮次jkey 值关键操作数组状态初始——8 2 4 9 3 6228 后移2 放到第 1 位2 8 4 9 3 6348 后移4 放到第 2 位2 4 8 9 3 6498 9无需移动2 4 8 9 3 6539、8、4 逐一后移3 放到第 2 位2 3 4 8 9 6669、8 后移6 放到第 4 位2 3 4 6 8 9这张表最大的作用是让你看清“后移”和“插入”是两件事后移是覆盖式地腾位置插入是在腾出的空位上写 key。很多人看动画觉得懂了一写代码就把后移和交换搞混。交换会破坏 key 的副本语义而这里 key 是单独保存的所以可以用覆盖操作。3.4 移植到 Python伪代码索引从 1 开始如何落地讲义伪代码的数组是 1-based而 Python 的 list 是 0-based。伪代码里 for j ← 2 to n到了 Python 要写成 for j in range(1, len(A))。最隐蔽的差异在 while 条件里伪代码用 i 0因为它的 0 号位不使用Python 里数组有效最小索引是 0所以条件要变成 i 0否则第一个元素永远不会被比较。常见错误示例如果 Pyhton 里沿用 i 0输入 [2, 1] 时key1i0因为 i 0 不成立循环直接退出1 被放回 A[1]整个数组没有任何变化。这个坑我第一次移植时就踩过属于典型的 off-by-one 问题。def insertion_sort(A): for j in range(1, len(A)): # 对应伪代码的 j ← 2 to n key A[j] # 取出当前要插入的元素 i j - 1 while i 0 and A[i] key: # 从右往左找插入点 A[i 1] A[i] # 元素后移腾出位置 i - 1 A[i 1] key # 把 key 放到正确位置 return A if __name__ __main__: print(insertion_sort([8, 2, 4, 9, 3, 6]))代码说明外层循环从第二个元素开始遍历内层循环里i 0 是 Python 下正确的边界保护A[i] key 决定是否继续后移。这个写法是原地排序空间复杂度 O(1)只用了 key 一个额外变量。时间上最坏情况和平均情况都是 O(n²)最好情况是 O(n)。算法导论里把这种“对基本有序数据很友好”的性质讲得很细实际上现代排序库比如 Python 的 Timsort在排序近乎有序的片段时也会利用插入排序的这一特性。4. 运行时间分析最坏、平均与最好情况4.1 输入规模 n运行时间参数化的起点讲义反复强调一个观点运行时间依赖输入本身。一个已经排好序的序列当然比乱序更容易排序。所以不能笼统说“插入排序很快”或“插入排序很慢”必须把运行时间表示成输入规模的函数。这就是参数化输入规模记为 n运行时间记为 T(n)。这里的 n 具体指什么对排序问题n 是待排序元素的个数。对于图算法n 可能是顶点数或边数。第一讲用排序做例子正是为了把“输入规模”这个概念钉死在最简单的情形上。我自己的习惯是拿到一个算法先问一句它的 n 是什么n 的物理含义都不清楚后面的复杂度推导全是空中楼阁。4.2 最坏情况给我们一个确定的保证“我们通常用最坏情况来分析算法”这是算法导论后续所有章节的地基。最坏情况定义很直接在所有长度为 n 的输入里算法花时间的最大者记为 T(n)。这样得到的结论是一个 guarantee——不管运气多差你的算法都不会慢过这个上界。工程上为什么偏爱最坏情况因为它可承诺。做调度系统时你不可能赌“今天的任务恰好都很好排”做数据库时你也不能假设查询条件永远命中最优索引。最坏情况分析给你一个稳定的预期就算输入形态完全失控系统也兜得住。这也是“上界保证”在实践里的意义。4.3 平均情况必须说清楚输入分布假设平均情况分析偶尔也要用但讲义点出一个关键前提需要假设输入的统计分布。对排序而言最常见的假设是“输入的所有排列等概率出现”。在这个假设下插入排序期望移动的元素数量大约是最坏情况的一半所以平均时间复杂度依然是 Θ(n²)只是常数项小一些。注意“平均”不是直觉上的“中庸水平”。没有分布假设平均值根本不存在。我见过不少新手把平均情况当成“大多数情况”这其实是个隐患。真实数据的分布大概率不是均匀随机排列而是带局部有序特征的。这时候平均情况分析可能与实际表现相差很远所以我一般只在输入分布明确可控的场景才用平均情况做决策。4.4 最好情况是糊弄自己bogus讲义里直接给最好情况打了一个标签bogus。原因是最好情况太容易被欺骗——只要设计一个“对特定输入跑得飞快”的慢算法它的最好情况就能很好看。比如一个排序算法可以特判“输入已经有序”时直接返回那它的最好情况是 O(n)但这能说明它好吗显然不能。最好情况的真正用途是提供一个下界参考比如插入排序在基本有序数据里确实有 O(n) 的实际表现这个特性可以让它作为其他算法的一个子程序。但评价一个算法的整体水平永远要用最坏情况做标尺。看懂这一节你就不会再犯“我的算法最好情况表现很好所以它很快”的认知错误。4.5 推导插入排序的 O(n²)一个可以复制的套路现在把前面几节落成一个具体推导。以最坏情况为例输入逆序排列即每个 key 都比已排序区里的所有元素小。那么第 j 轮外层循环内层 while 要比较并移动 j-1 次。总操作次数是T(n) Σ(j-1)j 从 2 到 n 1 2 ... (n-1) n(n-1) / 2展开后是 0.5n² - 0.5n去掉低阶项和常数系数增长量级是 Θ(n²)。这里的系数 0.5 在渐近分析里没有意义但推导过程的价值在于让你知道 O(n²) 不是背出来的是从循环结构里数出来的。平均情况类似随机排列输入时key 在已排序区中插入点的期望位置是整个区间的中点附近所以比较次数大约是 (j-1)/2求和得到约 n²/4同样收敛到 Θ(n²)。最好情况则是输入已经有序while 条件第一次判断就不成立每轮只做常数次操作总时间是 Θ(n)。我建议你把这套推导流程固化下来先确定基本操作——对排序来说就是“比较”和“移动”再确定最坏输入——逆序最后求和并保留最高阶项。这个套路可以平移到选择排序、冒泡排序也可以推广到后面章节的递归式分析。5. 看这套 MIT 笔记时最容易踩的坑索引、边界与保证的误读5.1 伪代码索引从 1 开始写代码时却从 0 开始现象照着讲义伪代码用 Python 写插入排序第一版把 while 条件写成 i 0结果数组第一个元素永远参与不了比较输入 [2, 1] 直接原样返回。原因讲义的数组是 A[1..n]0 号位被跳过所以 i 0 是安全边界而 Python 的 list 是 0-based0 号位是真实数据。边界条件在两种索引体系下天然差一个刻度。解决移植任何伪代码前先标明目标语言的索引起点再逐行换算循环边界。我现在的习惯是把对应关系写成注释放在代码块顶部例如“A[1..n] → A[0..n-1]”避免下次翻车。5.2 把“最坏情况复杂度”当成“运行时间总是这么多”现象和老同事讨论快排我说“最坏 O(n²)”他反问“那线上大数据量排序为什么没事”。原因最坏情况是一个上界保证不是对典型输入的预期。快排在大多数随机输入上收敛到 O(n log n)只有当输入结构恰好触发分区极度不均时才会退化到 O(n²)。混淆“理论上界”和“实战预期”会得出错误结论。解决描述算法时把“最坏情况时间复杂度”和“平均情况时间复杂度”分开说。真要评估线上的稳定性还得继续追问一句这种输入在真实流量里出现的概率有多大。5.3 平均情况脱离输入分布就是空谈现象有段时间我写算法笔记张口就是“平均 O(n log n)”但被问到“平均针对什么分布”时答不上来。原因平均值必须建立在概率模型上。排序的平均情况通常假设“所有排列等概率”但这个假设在真实业务数据里经常不成立局部有序和重复值反而常见。解决每次写“平均情况”时都先补一句“假设输入等概率分布”再说明这是理想化模型。如果拿真实数据做了采样就基于采样结果说话那比任何理想假设都有说服力。5.4 循环不变量不讲清楚看示例动画等于看热闹现象跟着讲义动画看插入排序眼睛跟着数字移动觉得每一步都懂关掉页面自己写代码时却错误百出。原因动画展示的是操作过程没有展示“为什么每轮开始前 A[1..j-1] 必然有序”这一逻辑保证。循环不变量才是正确性的根源。解决把循环不变量当成一道证明题来做初始化、保持、终止三个阶段逐个验证。至少选一个数组从 j2 到 n 手写每轮的数组状态和 key 值确认每轮结束后不变量都成立。这个过程不需要写代码铅笔和纸就行。5.5 老课件的年份感会挡住真正有价值的东西现象看到 Fall 2001 的课程编号第一反应是这都二十多年前的课了算法估计过时了。原因基础算法课讲的是复杂度分析方法和算法设计范式这些核心内容二十年间几乎没变。变化的是语言生态、工程场景和数据规模。年份只会影响课件里的工具和小例子不影响方法本身。解决把年份当成“历史现场”而不是“过期内容”。遇到符号或术语和新版 CLRS 不一致时以新版为准。网上流传的“算法导论习题答案”质量参差不齐尤其是第四章递推式相关的题目抄错率不低我建议只拿它当参考别当标准答案。6. 把经典课件变成自己的练习题三个可复用的落地习惯6.1 第一遍合上课件还原伪代码看完成功的演示和逐行解释先把讲义合上只凭“从第二个元素开始逐个往前插入到已排序区”这句话自己写出插入排序。写不出来就回头看再合上重写。这个过程能暴露你对边界条件的真实掌握程度。我的标准是一小时内能还原出伪代码并跑对示例数据才算真正理解这一讲。6.2 第二遍为每个边界条件设计反例针对插入排序构造五类输入空数组、单元素、逆序、已排序、全相同。全相同那个情况最容易忽略它的 while 条件中 A[i] key 不成立所以一个元素都不会移动复杂度是 O(n)这是插入排序的一个隐藏特性。把五个用例固化成一个测试函数每次改代码都跑一遍。6.3 第三遍用数据验证复杂度而不是只记公式随机生成 10 万长度的逆序数组跑插入排序记录耗时再跑 20 万长度观察时间是否大致变成原来的 4 倍。然后把输入换成随机数据再对比一次。这个实验比背公式更能建立对“增长量级”的直觉。要理解 O(n²) 到底意味着什么亲眼看到耗时随 n 膨胀比看任何证明都有效。从那以后我每次读算法课件都强制自己走一遍三重验证还原伪代码、构造边界反例、用数据验证复杂度。这个习惯帮我绕开了大量“看着懂了、上手就错”的坑也让我把这份 MIT 讲义从“浏览过的资源”真正变成了“长在手上的能力”。希望帮到你。本文还有配套的精品资源点击获取