@todo:
- 算法设计: 排序, 贪心, 分治, 动态规划, 回溯, 随机化
- 数学基础: 二分查找, 欧几里得算法, 快速幂算法
- 字符串匹配算法: KMP
- 图论算法:
- 拓扑顺序
- 最短路径: Dijkstra算法, Floyd-Warshall算法
- 最小生成树: Prim, Kruskal
- 搜索算法: BFS, DFS, A*搜索
- 几何算法: 向量, 凸包
- 快速傅里叶变换(FFT): 离散傅里叶变换
复杂度分析
几何级数 & 算数级数
- 几何级数: $$ 1 + 2^1 + 2^2 + … + 2^N = 2^(N+1) -1 ≈ 2^N $$
- 算术级数: $$ 1 + 2 + 3 + … + N = N(N+1)/2 ≈ N^2/2 $$
复杂度表示法
▶ 大O符号（英语：Big O notation） 用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。
设函数 $f(n)$ 代表某一算法在输入大小为n的情况下的工作量（效率），
我们将 $f(n)$ 与另一行为已知的函数 $g(n)$ 进行比较，
如果存在正数 C 和 n0，使得对于一切 $ n >= n0 $ 有： $ 0 <= f(n) <= C g(n) $，
则可以称 $f(n)$ 的渐进上界是 $g(n)$，记做 $ f(n) = O(g(n)) $，
▶ 小O符号： 类似大O，也用来表示「渐近上界」，
对于任意正数 C 和 n0，使得对于一切 $ n >= n0 $ 有： $ 0 <= f(n) < C g(n) $，
则可以称 $f(n)$ 的渐进下界是 $g(n)$，记做 $ f(n) = o(g(n)) $。
注意与大O定义的不同：
- 大O:「只要存在一个正数C」以及 $ f(n) <= C g(n) $。
- 小O:「任意正数C」以及 $ f(n) < C g(n) $。
- 两者都描述上限，但小O是更强有力的陈述，如果f∈o(g)，则f和g的增长率之间的差距比f∈O(g)时大得多。
例如, $ f(n) = n^2 + n $，则 $ f(n) $ 的复杂度可以记为 $ o(n^3) $
▶ 大Ω符号，读音：big omega，用另一个（通常更简单的）函数来描述一个函数数量级的「渐进下界」。
如果存在正数 C 和 n0，使得对于一切 $ n >= n0 $ 有： $ 0 <= C g(n) <= f(n) $，
则可以称 $f(n)$ 的渐进下界是 $g(n)$，记做 $ f(n) = Ω(g(n)) $
@ref: 007函数的渐近的界 - 算法基础 | Coursera
常用算法复杂度分析
算法中 $log$ 级别的时间复杂度都是由于使用了分治思想, 这个底数直接由分治的复杂度决定:
- 如果采用二分法, 那么就是 $log_2n$, 三分法就是 $log_3n$, 其他亦然;
- 不过无论底数是什么, 对数函数的渐进趋势是一样的, 所以通常忽略底数只用 $logn$ 表示;
场景复杂度的增长趋势如下图: $O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$
排序算法复杂度
数据结构复杂度
Big-O Cheat
@ref:: Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell
算法设计
贪婪
分治
回溯
@todo
动态规划
图论算法
深度优先 & 广度优先
@todo
拓扑排序
@todo
最短路径算法
@todo
无权最短路径
@todo
Dijkstra算法
@todo
网络流问题
@todo
最小生成树
@todo