复杂度速查

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

$n\le 10⟺\mathcal{O}(n!)$

$n\le 15⟺\mathcal{O}(3^n)$

$n\le 25⟺\mathcal{O}(2^n)$

$n\le 50⟺\mathcal{O}(n^5)$

$n\le 100⟺\mathcal{O}(n^4)$

$n\le 500⟺\mathcal{O}(n^3)$

$n\le 1000⟺\mathcal{O}(n^2\log n)$

$n\le 5\times 1e3⟺\mathcal{O}(n^2)$

$n\le 2\times 1e5⟺\mathcal{O}(n\sqrt{n})$

$n\le 1e6⟺\mathcal{O}(n\log n),\mathcal{O}(n)$

一些空间注意事项

map, set都会用到很多内存 (开了就会用到)

一般对于要求256mb来说，能开 $64\times 1e6$ 的 int以及 $32\times 1e6$ 的 int