1.根据数据范围倒推可用的算法时间复杂度
cpp在1s内，能算10^8，复杂度小于10^8即可
要熟记模板算法的复杂度，参考Y总的分享识记即可

2.时间复杂度分析
⑴循环
循环相互独立，一层循环就是O(n)，两层就是O(n^2)
如果循环不独立，比如AcWing 900.整数划分的背包方法
枚举可选数字，以及每个数字可以选几个，这两个循环放在一起是N*调和级数
调和级数的和是logn + 欧拉常数，所以这两重循环复杂度为nlongn

⑵递归
主定理：略
分析递归多少层，每层的复杂度
例如，归并排序为logn层，每层是O(n)复杂度，所以整体复杂度是O(nlogn)

⑶双指针
看似两层循环，但只用关注内层指针的循环次数，不超过n，所以复杂度是O(n)

⑷数据结构
链表：插入结点和删除头结点复杂度O(1)
栈和队列：O(1)
单调栈和单调队列：O(n)
KMP：O(n)
并查集：路径压缩最坏O(logn)，再加按秩合并O(loglogn)
堆排序：堆是完全二叉树，高度logn，加入或删除数据，复杂度与高度呈线性，O(logn)
哈希表：增删改查O(1)

⑸搜索问题
全排列：转化为树，每层结点数分别为n! (n-1)! (n-2)!
其他层相对最后一层是无穷小量，每个结点都要O(n)循环一遍数字，所以是O(n*n!)

⑹图论
图的搜索：dfs和bfs，每个点和每条边都会被遍历一次，所以O(n + m)
dijkstra算法：
朴素版，两重循环，都循环点，O(n^2)；
堆优化：操作m次堆，O(mlogm)，且m << n^2，也即O(mlogn)

bellman-ford：循环点再循环边，O(nm)
spfa：最短路，最差O(nm)，实际快很多；判断负环，O(nm)

floyd算法：三重循环，O(n^3)
prim算法：两重循环，O(n^2)
kruskal算法：边排序O(mlogm)，遍历边O(m)，O(mlogm)
染色法：图的遍历，dfs或bfs，O(n + m)
匈牙利算法：遍历点时，遍历边，复杂度O(nm)

⑺数学知识
判断质数：O(sqrt(n))
筛质数：两重循环相关，n*调和级数，O(nlogn)
补充：如果加优化，只筛质数倍数，O(nloglogn)
最大公约数：O(logn)
快速幂：k二进制有多少位，循环多少次，logk

(8)DP
DP计算量 = 状态数量 * 状态转移的计算量
背包问题：看循环或套公式
分组背包：状态数量nv，计算量O(n)，复杂度O(vn^2)，或者直接看三层循环
最长上升子序列Ⅱ:外层循环n次，内层二分logn次，O(nlogn)
蒙德里安的梦想：优化后，外层枚举列m，内层枚举当前列所有状态2^n，m*2^n
没有上司的舞会：状态数，所有边n-1，计算量O(1)，复杂度O(n)
滑雪：两维dp，状态数为n^2，计算量O(1)，复杂度O(n^2)

(9)贪心
排序 + 循环：O(nlogn)

3.空间复杂度分析
1 Byte = 8 bit
1 KB = 1024 Byte
1 MB = 10241024 Byte
1 GB= 10241024*1024 Byte

int 4 Byte
char 1 Byte
double, long long 8 Byte
bool 1 Byte

64 MB = 2^26 Byte
int: 2^26 / 4 = 2^24, 16000000, 1600w

灵活运用sizeof, 单位Byte, /1024转换为KB, 再/1024转换为MB，查看数组空间
操作系统优化：即使开了很大的数组，只要没用，系统就不会立刻开出来

递归和栈空间：快排递归logn层，会调用系统栈，额外空间O(logn)