时空复杂度分析

由数据范围反推算法复杂度以及算法内容

一般ACM或者笔试题的时间限制是1秒或2秒。在这种情况下，C++代码中的操作次数控制在 $107∼108$为最佳。

下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：

数据的大小范围 时间复杂度 常用算法
$n≤30$ 指数级别 dfs+剪枝，状态压缩dp
$n≤10^2$ $O(n^3)$ floyd，dp，高斯消元
$n≤10^3 $ $ O(n2)，O(n2logn)$ dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford
$n≤10^4$ $O(n\sqrt n)$ 块状链表、分块、莫队
$n≤10^5$ $ O(nlogn) $ 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
$n≤10^6$ $ O(n), 常数较小的 O(nlogn) 算法$ $O(n)算法$: 单调队列、 hash、双指针扫描、并查集，kmp、AC自动机
$常数比较小的 O(nlogn)的算法$：sort、树状数组、heap、dijkstra、spfa
$n≤10^7$ $O(n)$ 双指针扫描、kmp、AC自动机、线性筛素数
$n≤10^9$ $ O(\sqrt n)$ 判断质数
$n≤10^{18}$ $ O(logn)$ 最大公约数，快速幂，数位DP
$n≤10^{1000}$ $O((logn)^2)$ 高精度加减乘除
$n≤10^{100000}$ $ O(logk×loglogk)$ k表示位数，高精度加减、FFT/NTT

比赛中自己估算复杂度是否会超时会爆栈，首先要记住，时间复杂度为10^7即1千万左右在1s内可以稳当地跑出来, 10^8跑1s很勉强, 有的题目可能卡过去, 有的就卡不过去。计算时间复杂度就是分析基本语句的执行次数，所以在套模板前应当先想一想算法的时间复杂度并和题目给的数据套上一套，分析一波再去敲~

对于空间复杂度，其实一般就是看用到的数组要开多少。怎么算呢？拿int数组举栗，一个int要4字节即4b，然后1kb能开25个int，然后一般的题目要么给32768kb，要么给65536kb，所以前者可以开790w左右大小的数组，后者可以开1580w左右的数组，long long折半(395w, 790w)。float 4字节，double 8字节，能开多少不言而喻。