一、时空复杂度
1.用O表示
注意事项：i.保留最高次项，去掉其他内容
例O(3n^3+n+7)要写成O(n^3)
O(11n^4+5n+14)要写成O(n^4)
ii.去掉对数的底数
例O(n^2log2(n))要写成O(n^2log(n))
2.比较
O(1)<O(log(n))<O(根号n)<O(n)<O(n log(n))<O(n^1.5[n根号n])<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
二、主定理
T(n)=aT(n/b)+f(n)
f(n)>n^log_b(a),T(n)=O(n^log_b(a))
f(n)<n^log_b(a),T(n)=O(f(n))
f(n)=n^log_b(a),T(n)=O(n^log_b(a)log(n))
三、递归与搜索
搜索：dfs、bfs
优化dfs：固定层数
四、容器
数组：静态：array<int,10005>（C++11）
动态：vector
常用：set、map、priority_queue
少用：stack、deque