知识目录
基本数据结构
1 线性表
- 顺序表
- 链表
- 单链表
- 单循环链表
- 双向循环链表
- 跳跃表
- 并查集
2 堆栈、队列
- stack
- queue
- 优先队列、优先堆
- 多级反馈队列
3 哈希
4 递归
5 查找
6 排序
7 树
- 二叉树：以及各种遍历算法
- 哈夫曼树与编码
- AVL树
- B树与B+树
- 前缀树
- 红黑树
- 线段树
8 图
9 动态规划
基本算法
- DFS/BFS
- 递归
- 遍历（借助queue做BFS，借助stack做DFS）
- 二分法
- 排序
- 贪心
树
- 平衡树。插入、删除、搜索，O(ln n) ，且保持平衡树
- AA树：一种自平衡二叉树
图
- 最短路径算法
- A-star 算法，启发式
- Bellman-Ford 算法，适用于含负数权重的加权图 $O(n^3)$
- Dijkstra 算法，不含负数权重 $O(n^2)$
- 双向 Dijkstra 算法，减少后一半的搜索空间，因此比 Dijkstra 快一些
复杂度
一些定义：
定义1
$O(g)$代表一组函数，
$f\in O(g) \Leftrightarrow$
$ \exists n_0 ,c $使得$\forall n \geq n_0 , f(n) \leq cg(n)$
定义2
$\Omega (g)$的定义恰恰相反
$ \exists n_0 ,c $使得$\forall n \geq n_0 , f(n) \geq cg(n)$
定义3
$\Theta(g)=O(g) \cap \Omega(g)$
递归中复杂度主定理
如果递归计算量是这样的：
$T(n)=aT(n/b)+f(n)$
那么，复杂度为：
$\Theta(n^{log_{b} a})$
