全书思维导图
笔记
算法简介
大O表示法时间
O(log(n)) - 对数时间，各种分半的操作里，如二分查找
O(n) - 线性时间，简单查找、哈希表
O(n*log(n)) - 需要多个对数时间分治的算法，如快排
O(n^2) - 选择排序等
O(n!) - 旅行商问题
常见数据结构复杂度：
常见排序算法复杂度：
cheatsheet：
递归
每个递归函数有两个部分：
- base case
- recursive case
递归调用栈：
- 有上限
- 可以考虑 尾递归
快排
分而治之（Divide and conquer, D&C）
- 拆分成最小问题
- 最小问题解决条件归纳为base case
如快排：
partition
- pivot
- 扫过分类
- 返回左右两组
q-sort - sort调用
散列表
在C++ stl实现中使用bucket的概念，每个bucket有对应load_factor，超过之后自动rehash。
采用的hash算法为FNV hash
广度优先搜索
BFS breadth-first search
- 使用FIFO（queue）实现
- 非加权图BFS需要用一个结构去重避免环状结构
Dijkstra算法
解决加权图问题：
- 有向无环图
- 不可有负权边
贪婪算法
每步取当前最优
NP完全问题：
- 时间复杂度难以降低
- 无法分成小问题
- 问题设计序列、所有组合（尤其是集合覆盖或者旅行商问题）
动态规划
识别：
可拆分成小问题、依靠转移方程算
- 无重叠路径有向无环图（BFS）
- 有重叠（利用之前结果，DP）
其他
随机数算法：
- 布隆过滤器： 判断是否出现过
- HyperLogLog： 小空间存储大量记录