引言#

本系列基于MIT6.006(Spring 2011)与MIT6.046J(Spring 2015)及配套教材《算法导论》(introduction to algorithm). 课程的内容不包括教你怎么做出力扣和洛谷上的题目.

课程的内容包括:

1. 详细讲解基础算法和经典数据结构.
2. 进行算法设计.
3. 算法的合理性证明.
4. 研究算法的计算复杂度, 找到更优算法.

本课程希望你有一定的语法基础, 一点点计算机组成原理知识和一点点算法知识, 否则难度可能会过高.

建议先修(并不是必需的):

1. 一门计算机科学导论(推荐harvard CS50或MIT 6.00)
2. 一门语言入门课(推荐UCB CS61A或Stanford CS106B/X)

课程的python代码实现#

目录(待更新)#

1. 算法与计算模型
   1. 算法
   2. 计算模型
   3. 随机访问机模型
   4. 指针模型
   5. python的计算模型
2. 排序与树
   1. 插入排序
   2. 归并排序
   3. 堆与堆排序
   4. 二叉搜索树(BST树), BST排序
   5. AVL树, AVL排序
   6. 排序算法的复杂度下界, 计数排序, 基数排序
3. 哈希
   1. 字典
   2. 直接寻址表
   3. 哈希碰撞
   4. 动态哈希表
   5. 字符串匹配
   6. 开放寻址法
   7. 加密哈希
4. 数值与数论
   1. 整数算法
   2. Karatsuba乘法
   3. 平方根算法
   4. 牛顿切线法
5. 图论
   1. BFS
   2. DFS
   3. 拓扑排序
6. 最短路
   1. 单源最短路
   2. Dijkstra算法
   3. Bellman-Ford算法
   4. 加速Dijkstra
7. 动态规划
8. 计算复杂度
9. 数学相关
10. 凸包
11. 中值查找
12. FFT
13. VEB树
14. 开销均摊
15. 随机化
    1. 矩阵相乘
    2. 快速排序
    3. 跳跃表
    4. 全域哈希, 完全哈希
16. 最优化
    1. 区域树
    2. 进阶DP
    3. 全源最短路
    4. 最小生成树
    5. 最大流, 最小割
    6. 匹配算法
17. 网络流
18. 计算复杂度: P与NP
    1. NP完全问题
    2. 亚线性算法
    3. 近似算法
    4. 固定参数算法
19. 线性规划
    1. 单纯形法
    2. (待补充)
20. 其他进阶算法
21. 面向期末/考研的补充内容
22. 面向算法竞赛的补充内容