复杂度速查

一些算法比赛的时间复杂度要求

$n\le 10 \iff \mathcal{O}(n!)$ $n\le 15 \iff \mathcal{O}(3^n)$ $n\le 25 \iff \mathcal{O}(2^n)$ $n\le 50 \iff \mathcal{O}(n^5)$ $n\le 100 \iff \mathcal{O}(n^4)$ $n\le 500 \iff \mathcal{O}(n^3)$ $n\le 1000 \iff \mathcal{O}(n^2\log n)$ $n\le 5\times1e3 \iff \mathcal{O}(n^2)$ $n\le 2\times 1e5 \iff \mathcal{O}(n\sqrt{n})$ $n\le 1e6 \iff \mathcal{O}(n\log n), \mathcal{O}(n)$

一些空间注意事项

int: 4 bytes long long: 8 bytes double: 8 bytes long double: 16 bytes map, set都会用到很多内存 (开了就会用到) 一般对于要求256mb来说，能开 $64\times 1e6$ 的 int以及 $32\times 1e6$ 的 int