算法基础
⨭ 时间复杂度
| 类型 | 表达式 | 例子 |
|---|
| 常数 | O(1) | |
| 对数 | O(logn) | |
| 线性 | O(n) | |
| 线性方程 | O(nlogn) | |
| 二次方 | O(n^2) | |
| 多项式 | O(n^c) | |
| 指数 | O(2^n) | |
⨦ 排序算法
| 类型 | 最好时间 | 平均时间 | 最坏时间 | 空间 | 稳定性 |
|---|
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 桶排序 | O(n) | O(n) | O(n^2) | O(n) | 稳定 |
⦜ 数据结构
| 类型（平均） | 获取元素 | 查找元素 | 插入元素 |
|---|
| 数组 | O(1) | O(n) | O(n) |
| 链表 | O(n) | O(n) | O(1) |
| 双向链表 | O(n) | O(n) | O(1) |
| 栈 | O(1) | O(n) | O(1) |
| 堆 | O(1) | O(n) | O(logn) |
| 队列 | O(1) | O(n) | O(1) |
| 哈希表 | O(1) | O(1) | O(1) |
| 二叉搜索树 | O(logn) | O(logn) | O(logn) |
| 跳表 | O(logn) | O(logn) | O(logn) |
⦠ 递归公式
| 类型 | T(n) | 例子 |
|---|
| T(n)=T(n/2)+1 | O(logn) | 二分查找 |
| T(n)=2T(n/2)+1 | O(n) | 二叉树遍历 |
| T(n)=2T(n/2)+n | O(nlogn) | 归并排序 |
| T(n)=T(n−1)+n | O(n^2) | 插入排序 |
| T(n)=2T(n−1)+1 | O(2^n) | 回溯算法 |
⧅ 主定理
当 a≥1, b≥2, c>0 且 T(n) 在非负区间内满足 T(n) = aT(n/b)+O(nc)，假定 T(0)=0，T(1)=O(1)，则
| 类型 | T(n) |
|---|
| c<log(b)a | O(n * log(b)a) |
| c=log(b)a | O(n^c * logn) |
| c>log(b)a | O(n^c) |
⨭ 运算符优先级
基本规则
- 一元运算符优于二元运算符
- 乘除加减优于大部分运算符
- 位运算优于逻辑运算
Java
Java Operators
| 类别 | 列表 |
|---|
| 括号 | () |
| 前后缀与一元运算符 | ++, --, !, ~, +, - |
| 乘除加减 | *, /, +, - |
| 位移 | >>, << |
| 判断与比较 | >, >=, <, <=, ==, |
| 位运算 | &, ^, |, &&, || |
| 逻辑运算 | &&, || |
| 三元运算符 | ? : |
| 赋值 | =, +=, -=, ^=, >>= |
Python
Python Expressions
| 类别 | 列表 |
|---|
| 括号 | () |
| 阶乘 | ** |
| 前后缀与一元运算符 | ++, --, !, ~, +, - |
| 乘除加减 | *, /, +, - |
| 位移 | >>, << |
| 位运算 | &, ^, |, &&, || |
| 判断与比较 | >, >=, <, <=, ==, |
| 逻辑运算 | &&, || |
| 赋值 | =, +=, -=, ^=, >>= |
C++
C++ built-in operators, precedence, and associativity
| 类别 | 列表 |
|---|
| 括号 | () |
| 前后缀与一元运算符 | ++, --, !, ~, +, - |
| 乘除加减 | *, /, +, - |
| 位移 | >>, << |
| 判断与比较 | >, >=, <, <=, ==, |
| 位运算 | &, ^, |, &&, || |
| 逻辑运算 | &&, || |
| 赋值 | =, +=, -=, ^=, >>= |
⦧ 表达式
| 类型 | 表达式 | 结果 |
|---|
| 调和级数 | 1 + 1/2 + 1/3 … + 1/n | - |
| 自然对数 | (1 + 1/n) ^ n | e (n→∞) |
| 等差数列 | n1 + n2 + n3 + n4 … + n | n * (n1 + n) / 2 |
| 等比数列 | n1 + n2 + n3 + n4 … + n | n1 * (1 - q ^ n) / (1 - q) |
| 卡特兰数 | f(n)=f(0) * f(n-1) + f(1) * f(n-2) … + f(n-1) * f(0) | - |
⨦ 链表
⦜ 二叉树
⧉ 类型
| 类型 | 简介 | 节点数量 | 树的高度 |
|---|
| 一般二叉树（Binary tree） | 节点数量为 N，树高度为 H | 每一层最大节点数量为 2^H，最底层最大节点数量为 N | 0 <= H <= N |
| 完全二叉树（Complete binary tree) | 除了最后一层的右边，其他节点都已经填满 | 2^(H-1) <= N <= 2^H - 1 | 0 <= H <= log(N) |
| 满二叉树（Full binary tree） | 每个节点有零或者两个子节点 | 2 * H + 1 <= N <= 2^H - 1 | log(N) <= H <= N/2 |
| 完美二叉树（Perfect binary tree） | 每个节点有零或者两个子节点且在同一层 | 2^(H+1) - 1 | log(N) |
⨦ 遍历方式
| 类型 | 例子 |
|---|
| 前序遍历 | 父节点 -> 左节点 -> 右节点 |
| 中序遍历 | 左节点 -> 父节点 -> 右节点 |
| 后序遍历 | 左节点 -> 右节点 -> 父节点 |
| 层序遍历 | 第一层 -> 第二层 -> 第三层 |
⦠ 图论
| 类型 | 简介 |
|---|
| 图（Graph） | 节点数量 V (vertice)，边 E（edge） 0 <= E < V ^ 2 |
| 无向图（Undirected graph) | node 节点没有方向，0 <= E < V * (V-1) / 2 |
| 有向图（Directed graph） | node 节点有方向，0 <= E < V * (V-1) |
| 简单图（Simple graph） | 没有自环（self loop），没有重复边的无向图 |
| 非简单图 | 可能包含自环（self loop）和重复边 |
| Walk | 节点 A 到节点 B 的路径，例如 A -> C -> D -> C -> B |
| Path | 不使用重复节点下，节点 A 到节点 B 的路径，例如 A -> C -> B |
| degree | 连接的节点数量，对于有向图包括 in-degree 与 out-degree |
| 算法 | 介绍 | 允许负权重值 | 可以检测出负权重环 | 时间复杂度 |
|---|
| Dijkstra | 单源带权重的有向图最短路径 | ❌ | ❌ | O((V+E)logV) |
| Bellman-Ford | 一般情况下的单源带权重的有向图最短路径 | ✅ | ✅ | O(VE) |
| Floyd-Warshall | 所有结点对最短路径 | ✅ | ❌ | O(V^3) |