【MIT公开课】6.006 算法导论（完结·中英字幕·机翻）

本课有3大内容：

1.效率与复杂度

2.程序的可延展性

3.一些经典数据结构与经典算法（如排序和匹配，但算法课更推荐6.046）

Python的使用与实现是本课一大亮点

具体又分成8大块：

1.算法思维：peaking finding(第一集 15:00 开始)特殊数据寻找/特殊数据点/函数零点/导数零点/函数最值……

2.sorting & trees 排序

3.Hash 哈希比较

4.RAS加密

5.Graph图论与魔方

6.short-path最短路径

7.动态编程/动态规划

8.一些进阶话题（与6.046甚至是6.854、6.851衔接）

本课前置课程6.042离散数学，主要需要关于渐进复杂度的讨论

peaking finding （找最值/峰值）

第一节主要是以peaking finding为例，让学生体验什么叫算法分析，对应课本第二单元

首先需要一个实用的，不讲废话的”峰值“定义：a,b,c,按顺序，满足a<=b,c<=b,b是峰值

对一维问题：

1.遍历法 复杂度为order n 线性复杂度

2.二分法 复杂度为order log2(n) 对数复杂度

对二维问题：

1.遍历法 order (nm) =order (n^2)

2.简单二分法 无法使用 因为二维问题存在局部极值

3.修正后二分法 增加局部极值相互比较的步骤

lec02

第二节开头是一个大杂烩，介绍课本前四节中涉及的但在第一节课中没有来得及提及的定义，比如什么是算法

文件距离例子：

使用内积定义距离（度量metric) ，显然还会带有角度。

d(v1,v2)=v1*v2=sum of v1[i]*v2[j]

需要考虑归一化问题

lec03

1.排序的用途

2.

3.

本节课正式进入算法分析，对课本前四单元内容进行扫尾，特别是图解演示nlogn复杂度

（中文版教材，排版奇怪，需要注意与英文原版对照）

lec04

这是足以高潮的 一节课（痴汉脸）

首先是数据结构，数据的结构，点的结构，几何的结构：

”如同在数学中一样，集合也是计算机科学的基础。不过数学中的集合是不变的，而算法所操作的集合却可以随着时间的改变而增大、缩小或产生其他变化。我们称这种集合是动态的。“

动态集合支持的操作：search查找、insert插入、delete删除

显然，计算机科学的基础图论和集合论的条件更为宽松的。

哈佛抽象代数公开课里，教授用”人是看不见自己的未来的，但我能看见你们的未来，期末的未来“ 一句玩笑话，正式引入了群表示论，表示论”换个角度看世界“的思想，如此简单，如此有效

在计算机科学中，我们的研究对象/我们的系统和宇宙（物理化学用语）/我们的集合、集合中的元素具有离散的结构，或者叫没有结构。

没有，意味着我们可以任意揉搓，当成一笔画问题，拉成一条线，他就是数组array、栈、队列，适当的拓扑形变就变成圆，一个有限域，存储在有限的内存空间

加一个映射，直线就映射成二叉树，如果不限制映射的模样，也就有了图

本节用一节课时间，讨论了课本第六单元，堆排列，讨论另一个视角下的数列——二叉树，利用新结构的特殊性质，加速排序过程，变一维问题为二维问题，增加了解决问题的灵活度