麻省理工学院公开课：算法导论_贪婪算法，最小生成树

简介：

[第1课] 课程简介及算法分析

课程简介及算法分析

[第2课] 渐近符号、递归及解法

渐近符号、递归及解法

[第3课] 分治法（1）

分治法（1）

[第4课] 快排及随机化算法

快排及随机化算法

[第5课] 线性时间排序

线性时间排序

[第6课] 顺序统计、中值

顺序统计、中值

[第7课] 哈希表

本课为我们引入了一种简单而高效的数据结构——哈希表（又译作散列表）。课堂上，教授为我们介绍了哈希表的基础知识，讲述除法哈希法、乘法哈希法以及开放寻址法，并对它的复杂度做了分析。除此之外，他还就如何高效地运用哈希表、如何处理可能遇到的“碰撞”问题等进行了讨论。

[第8课] 全域哈希和完全哈希

本课继续深入学习哈希表，这节课的内容主要是哈希表的高级运用。为了应对哈希表发生“碰撞”的问题，教授这次给我们带来了全域哈希和完全哈希。这节课里涉及到了很多美妙的数学知识，算法的证明过程相当有趣。学习这节课的内容，将会使你的哈希表更为高效、更为稳定。

[第9课] 二叉搜索树

本课为我们带来了一种常用的数据结构——二叉搜索树。这种数据结构有着媲美快速排序的速度，同时又能完成插入、删除和查找等动态化的操作，高效而又易于实现。教授将在本节课为我们讲解二叉搜索树的原理，运用巧妙的数学知识来证明它的高效性。二叉搜索树有什么优缺点，随机化二叉树又如何解决问题，这节课都会一一为你解答。

[第10课] 平衡搜索树

如果搜索树的结构不能保持平衡，它的运行效率将会大打折扣。这节课上，我们将会着重学习一种著名而实用的平衡树算法——红黑树。教授将会从红黑树的运行效率入手，再扩展到实际构造和维护红黑树。讲解过程中加入了大量的图例，更加方便大家消化吸收。

[第11课] 扩充的数据结构、动态有序统计和区间树

在实践中，我们对数据结构的功能需求并不仅仅局限于基本的插入、删除和查询操作。为了使数据结构能满足我们的需求，第11课里，教授给我们讲授了如何扩展一个现有的数据结构。教授以红黑树的几种扩展算法为例，讲解了的扩展的方法论以及策略。掌握了这些以后，你实现新功能起来将会更加得心应手。

[第12课] 跳跃表

《算法导论》第12课里我们将学到一种简单而又十分有趣的动态搜索数据结构——跳跃表。这种数据结构的优势在于它易于实现，而且很好地保证了它总是能高效运作。教授通过纽约地铁的例子引入，生动地讲解了跳跃表的构造、查询过程。同时，他给我们分析了跳跃表“有高概率”的高效性质，用数学给我们展示了它的强大之处。

[第13课] 平摊分析，表的扩增，势能方法

有时候，就算是再大的困难，只要人人都愿意出一份力，也能大事化小。而算法的分析也有这种情况。有时候某几步操作相当复杂，但是如果将一系列操作平均起来，它的代价可能也并不是那么的高。《算法导论》第13课里，教授就给我们讲授了几种平摊分析的方法，包括聚集法、记账法还有势能法。这些都是算法分析的重要方法，掌握它们将能让我们更加准确地评估算法优劣性。

[第14课] 竞争性分析，自组织表

我们将要关注一种在线算法的分析方法——竞争分析。实际应用中，数据不会总是全部出现在我们面前，而是一个接一个地出现。这样我们就不能安排最好的对策来处理问题。但是我们也可以证明，在线算法并不会跟最优算法差太远。这节课上，教授将会结合上一节课中平摊分析的内容，给我们展示这一个相当精彩的分析过程。

[第15课] 动态规划，最长公共子序列

我们将会学到一个常用的优化算法的技术——动态规划。它是一种解决最优解问题的一种方法，它还是信息竞赛选手必须掌握的技能。在这一节课上，教授会围绕最长公共子序列（LCS）的实现问题来讲解可动态规划算法的特征，还有动态规划的一般优化思路和方法。通过应用动态规划，我们的程序性能将会获得显著的提升。

播放中

[第16课]贪婪算法，最小生成树

《算法导论》第16课中，教授给我们带来了一种新的算法思想－－贪婪算法的思想。和动态规划一样，贪婪算法是一种求解最优问题的方法。它强调通过寻找局部的最优解，从而节省大量的时间和资源。这次课里，教授会围绕图的最小生成树的问题，分析贪婪算法的思想和应用条件。我们还会看到一个贪婪算法实例－－Prim算法，看看它又是如何为AT＆T公司取得垄断的地位。

[第17课] 最短路径算法：Dijkstra算法，广度优先搜索

从第17节的《算法导论》开始，MIT的教授将会为我们上演精彩的最短路径三部曲。在第一乐章里，我们会学习到一个非常著名的求解最短路径算法－－Dijkstra算法。教授首先会给我们讲解最短路径的特殊性质，然后针对一种非负权值的的最短路径问题，给我们详细讲解Dijkstra算法的做法，以及对它的正确性进行深度的分析。

[第18课] 最短路径算法：Bellman和差分约束系统

承接上一回，《算法导论》第18集是最短路径三部曲的第二乐章。在这一节课上，教授给我们讲解的是能够处理负权值最短路径问题的算法——Bellman-Ford算法。Bellman-Ford算法不仅能够检测图中的负权环，同时它还能解决线性规划的差分约束问题。教授将给我们详细讲解Bellman-Ford算法的流程，并证明它的正确性。这些内容都会跟下一节课的内容息息相关。

[第19课] 最短路径算法：点的最短路径

《算法导论》的第19课终于到了最短路径三部曲的高潮。这次我们将会着眼于全点对最短路径问题，教授将会给我们用三种算法来解决这个问题。除了上节课我们学到Bellman-Ford，我们还会用一个精彩的技巧，将问题与矩阵乘法联系起来，也就是Floyd-Warshall算法。而最后，我们将会学习最强大的Johnson算法，来为最短路径三部曲唱响最华丽的解答。

[第20课] 高级课题并行算法（一）

《算法导论》课程的最后将介绍一些高级课题。本课介绍的是并行算法。解答了1、面对多核处理器技术的不断革新，对算法如何优化，使得效率可以倍增；2、如何来分析并行算法对运行速度的提升；3、著名的国际象棋人工智能“深蓝”曾经的宿敌是谁。

[第21课] 高级课题并行算法（二）

《算法导论》第23课将承接上一回，这一次教授将给我们介绍并行算法的实际应用，讲解如何使用多线程来实现算法的并行化。课上教授将会用矩阵相乘以及归并排序为例子，从算法框架到运行时间分析来教大家实际认识多线程并行算法。

[第22课] 高级课题缓存参数无关算法

承接上一课，本课教授介绍了缓存敏感算法和缓存参数无关算法的概念，首先从计算机的缓存-内存分层存储模型引入，讨论了缓存参数无关算法的性质和分析上的优越性，并且具体讨论了在分层存储模型中的算法性能分析和存储设计。

[第23课] 缓存无关算法2

《算法导论》课程的最终章将继续深入分析缓存参数无关算法，教授将在本次课上为我们讲解多路归并排序算法是如何与缓存参数无关算法模型相结合。他将用一种名为K漏斗的特殊数据结构从实现到分析来给我们展示如何更高效地利用缓存来优化算法设计。

字幕纠错

对字幕纠错要登录哦！

相关推荐

1萨科技的哈时刻的

麻省理工学院公开课：算法导论