麻省理工学院算法导论讲座纪要(2009)

你们可能都知道，我看了整个麻省理工学院算法入门课程的讲稿，并把它贴了出来。在这篇文章中，我想总结一下讲座中涉及的所有主题，并指出其中一些最有趣的地方。

实际上，在我写这篇文章之前，我已经开始写一篇名为“我从麻省理工学院算法导论中学到的最酷的东西”的文章，但我很快意识到，我所做的只是列出了每篇文章中的主题，而不是真正指出最酷的东西。因此，我决定先写一篇总结文章(我答应这样做)，然后才写一篇关于真正令人兴奋的主题的文章。

说到总结，我一共看了23场讲座，发表了14篇博文。我花了将近一年的时间才在这里出版。以下是所有帖子的列表：

我现在要把每堂课都看一遍。他们需要相当多的数学知识才能理解。如果你对自己的数学技能不确定，我建议你读一读库恩斯的“具体数学”一书。它绝对包含了理解这门课程所需的所有数学知识。

如果你是学生，或者即使你不是，你也绝不能错过任何课程的第一堂课，永远不要错过！第一堂课告诉你期望从课程中得到什么，它将如何教授，它将涵盖什么，教授是谁，前提条件是什么，以及其他一些重要而有趣的事情。

在本讲座中，您还将认识查尔斯·E·莱瑟森教授(《CLRS》的作者)，他解释了以下主题：

我个人觉得这个清单比节目的表现更重要。这些因素是模块化、正确性、可维护性、安全性、功能性、健壮性、用户友好性、程序员的时间、简单性、可扩展性、可靠性和可扩展性。

第二堂课由埃里克·德梅因主持。他是麻省理工学院历史上最年轻的教授。

这堂课中有趣的一点是(O，？，？，O，？)。至(？，？，=，<；，>；)。

例如，如果我们说f(N)=O(N 2)，那么通过类比，我们可以认为它是f(N)？C·n 2，即函数f(N)总是小于或等于c·n 2，或者换句话说，它是由函数c·n 2在上面有界的，这正是f(N)=O(N 2)的意思。

第三讲分而治之的算法设计方法及其应用。分治方法通过1)将问题分解成多个子问题(分割步骤)，2)递归地求解每个问题(征服步骤)，3)合并解(合并步骤)来解决问题。

我对计算斐波纳契数的四种算法印象最深。我实际上在我的出版物“寻找斐波纳契数的线性时间算法”中写过其中的一个，解释了这个算法在实践中是如何实际上是二次的(但在理论上是线性的)。

第四堂课完全是关于快速排序算法的。它是大多数计算机系统中用于排序的行业标准算法。你只要知道就行了。

我喜欢将快速排序算法中的分区子例程随机化的想法如何导致独立于元素顺序的运行时间。确定性快速排序总是可以输入触发最坏情况运行时间O(N2)的输入，但随机化快速排序的最坏情况运行时间仅由随机数生成器的输出确定。

我曾经写过一篇关于快速排序的文章，名为“三个漂亮的快速排序”(Three Beautiful Quicksorts)。在那篇文章中，我总结了乔恩·本特利(Jon Bentley)对快速排序运行时间的实验分析，以及当前的快速排序算法在业界库(如提供qort函数的c标准库)中的表现。

第五课继续讲解排序，并讨论了是什么将排序的运行时间限制为O(n·lg(N))。然后突破了这一限制，给出了几种线性时间排序算法。

这里最有趣的主题是如何将任何比较排序算法转换为决策树(反之亦然)，这限制了我们排序的速度。

第六课讨论顺序统计量问题--如何在n个元素中寻找第k个最小的元素。朴素的算法是对n个元素的列表进行排序，然后返回排序列表中的第k个元素，但这种方法使其运行时间为O(n·lg(N))。这堂课展示了如何为这个问题构建一个随机的、线性时间的算法(在期望中)。

本讲座的一个有趣之处在于，顺序统计量的最坏情况、确定性、线性时间算法没有在实践中使用，因为与随机线性时间算法相比，它的性能较差。

这是两节课中关于散列的第一节课。它介绍了哈希和各种冲突解决策略。

关于散列的第二堂课。它解决了散列的弱点-对于任何散列函数的选择，都存在一组错误的键，它们都散列为相同的值。敌手可以利用这一点攻击我们的程序。通用散列解决了这个问题。本课程讲解的另一个主题是完美散列-给定n个键，如何构造一个大小为O(N)的散列表，其中搜索需要O(1)保证。

本讲座主要讨论随机构建的二叉搜索树。(它假定您知道什么是二叉树。)。与通用散列类似(请参阅上一课)，当您需要从不可信的数据构建树时，它们可以解决问题。结果表明，随机构建的二叉搜索树的期望高度仍然是O(lg(N))，更准确地说，它预计至多是3.lg(N)。

本课程中最令人惊讶的想法是，二叉搜索树排序(在本课程中介绍)执行与快速排序相同的元素比较，也就是说，它们产生相同的决策树。

这是关于搜索树的第二堂课。它讨论了自平衡树，更具体地说，红黑树。它们以这样一种方式平衡自己，即无论输入什么，它们的高度始终是O(lg(N))。

第十一讲讲解如何从现有的数据结构中构建新的数据结构。例如，如何构建可以快速更新和查询第i个最小元素的数据结构。这就是动态顺序统计量的问题，一个简单的解决方案是增加二叉树，例如红黑树。另一个例子是区间树-如何快速找到与其他一些区间(如4-11和8-20)重叠的区间(如5-9)。

扩充数据结构需要极大的创造力。首先，您需要找到一个底层数据结构(最简单的步骤)，然后想办法用数据来增强它，让它做您想做的事情(最困难的步骤)。

这堂课讲解跳过列表，这是一种简单、高效、容易实现的随机搜索结构。它的性能与平衡二叉搜索树一样好，但更容易实现。Eric Demaine说他在上课前40分钟就实现了它(10分钟实现，30分钟调试)。

在这堂课中，Eric从头开始构建这个数据结构。他从一个链表开始，构建到一对链表，再到三个链表，直到找到实现对数搜索时间所需的最佳链表数量。

接下来，他继续解释如何通过算法构建这样的结构，并证明在此数据结构中的搜索确实很快。

摊销分析是一种技术，它表明即使一个操作序列中的几个操作成本很高，总体性能仍然很好。向动态列表(如Python中的列表)添加元素就是一个很好的例子。每次列表都满了，Python就不得不分配更多的空间，这是非常昂贵的。摊销分析可以用来显示每个插入的平均成本仍然是O(1)，即使Python偶尔需要为列表分配更多的空间。

这堂课集中在自我组织的清单上。自组织列表是对自身重新排序以改善平均访问时间的列表。目标是找到一种最大限度减少总访问时间的重新排序。例如，每次访问某个元素时，它都会移到列表的前面，希望很快就能再次访问。这就是所谓的前移启发式算法。

竞争分析可以用来从理论上推断将项目移到最前面这种战略的表现如何。

这堂课是关于动态规划算法设计技术的。它是一种表格方法(包括构建一个表或表的某一部分)，可以大大加快算法的运行时间。

这堂课的重点是最长公共子序列问题，首先是暴力算法，然后是递归算法，最后是动态规划算法。暴力算法对字符串的长度是指数的，递归算法也是指数的，但动态规划解是O(n·m)，其中n是一个字符串的长度，m是另一个字符串的长度。

这堂课中最有趣的事情是两个标志，表明问题可以用动态编程来解决。它们是最优子结构和重叠子问题。

第一种是指问题的最优解包含子问题的最优解。例如，如果z=lcs(x，y)-z是问题LCS(x，y)的解-那么z的任何前缀都是x的前缀和y的前缀的LCS的解(z的前缀是子问题的解)。

第二个问题的意思正如它所说的，这个问题包含许多重叠的子问题。

这堂课通过最小生成三个问题介绍了贪婪算法。最小生成树问题要求找到一棵以最小边权连接图的所有顶点的树。起初，动态规划解法似乎可以有效地解决这个问题，但如果仔细分析，可以注意到该问题表现出另一个强大的性质--每个子问题的最优解都会导致全局最优解。因此，它被称为贪婪，它总是为子问题选择最好的解决方案，而从不考虑整个问题的总体情况。

这堂课开始了关于最短路径算法的三部曲。在第一部分中，我们讨论了单源最短路径算法。问题可以描述如下--如何通过行驶最短的距离从图上的一点到达另一个点(想想公路网)。Dijkstra'；的算法有效地解决了这个问题。

这里最有趣的是，Dijkstra用于未加权图的算法减少到广度优先搜索算法，该算法使用FIFO而不是优先级队列，因为不再需要跟踪最短距离(所有路径都具有相同的权重)。

关于最短路径的三部曲的第二讲涉及可能具有负边权的单源最短路径。贝尔曼-福特算法解决了负边图的最短路问题。

三部曲的最后一课讨论所有对最短路径问题--确定给定图形中每对顶点之间的最短距离。

这里一个有趣的地方是，如何将运行在O((顶点数)3)内的Floyd-Warshire算法转换为类似于Strassen的算法来计算图的传递闭包(现在它运行在O((顶点数)lg7)内)。

这是多线程算法分析的入门课程。它解释了多线程算法中使用的术语，如工作、关键路径长度、加速比、并行性、调度等。

第二讲并行算法，介绍如何设计和分析多线程矩阵乘法算法和多线程排序。

缓存无关算法考虑了到目前为止在所有算法中都忽略的东西，特别是缓存。可以转换为有效使用高速缓存的算法将比不使用高速缓存的算法执行得更好。这堂课的全部内容都是关于如何在内存中以最大限度地减少内存传输的方式布局数据结构。

这是本课程的最后一堂课。它继续介绍缓存无关算法，并展示了如何将二叉搜索树存储在内存中，以便在搜索时最大限度地减少内存传输。它以缓存不经意的排序结束。

这是整个课程中最复杂的一堂课。理解k-漏斗数据结构需要一天的时间。

接下来，我会把我在麻省理工学院线性代数课程上的笔记贴出来。起初，我以为我应该把“线性代数”发到一个单独的博客栏目上，这个栏目不会出现在RSS提要中，但后来我又想了想，得出的结论是，每个有能力的程序员都必须懂线性代数，因此把它们放到提要中是值得的。即使你不懂线性代数，你也可以成为一名优秀的程序员，但如果你想要解决重大问题并有所作为，那么你绝对必须懂这一点。

敬请关注！(更新：第一堂课上了-第一课：线性方程的几何。)