算法 | 时空复杂度 | Birdy の小窝

时间复杂度

评测机大概 $1s$ 最多运行 $1$ 亿次，即 $1e8$

时间复杂度一般小于 $1e7 \sim 1e8$ 就可以

$2^{20} ≈ 10^6$

$2^{16} = 65536$

$2^{15} = 32768$

$2^{63} = 10^{18}$

源自 $y$ 总，指路：原文链接

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

对于空间复杂度

$int ~ =~4 ~ Byte$

$char ~ =~1 ~ Byte$

$long~ long ~ =~8 ~ Byte$

$float ~ =~4 ~ Byte$

$double ~ =~8 ~ Byte$

$64MB = 6\times 2^{20}Byte = 6.4 \times 10^{7} Byte$

可以开 $1.6 \times 10^{7}$ 个 $int$

$n < 10^5$ 时，用 $scanf,printf,cin,cout$ 差不多

$n \ge 10^5$ 时，用 $scanf,printf$

如果想用 $cin, cout$，需要关闭同步

#include <iostream>

using namespace std;

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
}