Algorithm
1 算法引论
Introduction to Algorithm
-
程序 = 算法 + 数据结构
-
将数据结构与算法类比为拼装积木。 数据结构就是积木的形状和数量， 算法就是拼积木的步骤。
-
辗转相除法
1.1 复杂度分析
Complexity analysis
- 执行次数
- Big-O
1.2 迭代与递归
Iteration and Recursion
- 改进：保留中间结果
数据结构
数组与链表
栈与队列
哈希表
树
二叉树遍历
- 中根次序遍历，左中右
- 先根次序遍历，中左右
- 后根次序遍历，左右中
堆
图
图的遍历
访问顺序是放入，检测顺序是弹出， - 广度优先遍历 (BFS)，队列，广度优先 - 深度优先遍历 (DFS)，递归，栈，深度优先 - 深度检索 (D_Search)，改造 BFS ，栈，广度优先
对策树
α-β 剪枝，求 max 是 α 值，求 min 是 β 值， max 下是 β 截断， min 下是 α 截断。 左根右。
搜索
排序
分治
二分搜索
归并排序
奇数情况，划分之后奇数在前。
快速排序
左边指针先移动，前后指针交叉之后，将中枢元素与后指针所在位置交换。
棋盘覆盖问题
在划分之后无特殊顶点的子棋盘靠近中心的地方放一个 L 型骨牌。
贪心
度量标准。
背包问题（部分可装入）
带有期限的作业排序
最优归并模式
哈夫曼编码。
最小生成树
Prim 算法
Kruskal 算法
破圈法
单源最短路径
动态规划
- 重复子问题
- 从底向顶
- 数组，滚动数组
多段图问题
每对结点之间的最短路径
Floyd 算法