acwing算法基础之时空复杂度分析
目录
- 1 基础知识
- 2 模板
- 3 工程化
1 基础知识
（一）
由数据范围反推算法。
C++中题目给出的要求时间是1秒或2秒计算出结果，而1秒内C++可以执行 1 0 7 ∼ 1 0 8 10^7 \sim 10^8 107∼108次操作。故需要把时间复杂度控制在 1 0 8 10^8 108以内。
给定数目范围 n n n，有如下情况，
- 当 n ≤ 30 n\leq 30 n≤30时，指数级别，可以考虑的算法有：dfs+剪枝，状态压缩dp。
- 当 n ≤ 1 0 2 n \leq 10^2 n≤102时，可以接受的最大的时间复杂度为 O ( n 3 ) O(n^3) O(n3)，那么可以考虑的算法有：floyd，dp。
- 当 n ≤ 1 0 3 n\leq 10^3 n≤103时，可以接受的最大的时间复杂度为 O ( n 2 l o g n ) O(n^2logn) O(n2logn)，那么可以考虑的算法有：dp，二分。
- 当 n ≤ 1 0 4 n \leq 10^4 n≤104时，可以接受的最大的时间复杂度为 O ( n n ) O(n\sqrt{n}) O(nn)，那么可以考虑的算法有：块状链表。
- 当 n ≤ 1 0 5 n\leq 10^5 n≤105时，可以接受的最大的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)，那么可以考虑的算法有：排序算法（快速排序、归并排序、堆排序），线段树，树状数组，set/map，heap，dijkstra + heap，spfa，求凸包，求半平面交，二分。
- 当 n ≤ 1 0 6 n \leq 10^6 n≤106时，可以接受的最大的时间复杂度为常数较小的 O ( n l o g n ) O(nlogn) O(nlogn)，那么可以考虑的算法有：hash，双指针扫描，kmp，AC自动机，排序算法（快速排序、归并排序、堆排序），树状数组，heap，dijkstra，spfa。
- 当 n ≤ 1 0 7 n\leq 10^7 n≤107时，可以接受的最大的时间复杂度为 O ( n ) O(n) O(n)，那么可以考虑的算法有：双指针扫描，kmp，AC自动机，线性筛素数。
- 当 n ≤ 1 0 9 n\leq 10^9 n≤109时，可以接受的最大的时间复杂度为 O ( n ) O(\sqrt{n}) O(n)，那么可以考虑的算法有：判断质数。
- 当 n ≤ 1 0 18 n\leq 10^{18} n≤1018时，可以接受的最大的时间复杂为 O ( l o g n ) O(logn) O(logn)，那么可以考虑的算法有：最大公约数。
（二）
计算时间复杂度的小技巧，有
- 看循环，有几重循环就是n的几次方的时间复杂度。
- 并查集的时间复杂度是 O ( n l o g n ) O(nlogn) O(nlogn)。
- 动态规划问题的计算量 = 状态的数量 * 状态转移的计算量。
2 模板
暂无。。。
3 工程化
暂无。。。