复杂度理论

四个复杂度

1. 时间复杂度 - 核心考察点
2. 空间复杂度 - 次要考察点
3. 编程复杂度 - 能看得懂
4. 思维复杂度 - 能想得出

双指针线性复杂度

但有的时候，很明显的小数据的情况下，可以略微损失一点时间复杂度来降低编程复杂度，提高可读性

时间复杂度

只考虑最高项，不考虑常数项和系数项

O(2^N+N2) = O(2^N)

O(N^3+1000N2) = O(N^3)

O(logN) = O(log(N^2)) = O(log4(N))

Omax(n, m) = O(n+m)

P 问题 Polynomial

（多项式问题）

• On，On2，On3
• O1，On0.5, Om+n
• Ologn，Onlogn

NP 问题

• O2n，On^n, On!

分类

• O(IogN)二分法比较多

• O(N0.5)分解质因数（极少）

• O(N)双指针，单调栈，枚举法

• O(NlogN)排序，O(N*logN的数据结构上的操作)

• O(N2),O(N3),动态规划等

• O(2n)组合类(combination)的搜索问题

• O(N!)排列类(permutation)的搜索问题

根据时间复杂度来倒推算法

On 算法有

1. 双指针算法：最常见，频率远大于后面的所有算法的和
2. 打擂台算法：找最大值（一开始赋值成负无穷，每次把最大的打下来）
3. 单调栈算法：四五道题稍微多一些
4. 单调队列算法