时间复杂度 -> 算法
zhujianheng
·
·
个人记录
数据范围 时间复杂度 求解方法
$n \le 25$ $O(2^n)$ 暴力 DFS，状压 DP。
$n \le 50$ $O(n^5)$ 高维 DP。
$n \le 100$ $O(n^4)$ 高维 DP。
$n \le 500$ $O(n^3)$ 三维 DP，区间 DP，Floyd。
$n \le 8000$ $O(n^2)$ 二维 DP，区间 DP，分段 DP，各种题的暴力算法，DP 计数，求组合数，Prim，Dijkstra 原版。
$n \le 10^5$ $O(\dfrac{n^2}{w}),O(n \sqrt n \log n)$，分块 + lower_bound，bitset，树套树（常数太大）。
$n \le 4 \times 10^5$ $O(n \sqrt n)$，分块，莫队。
$n \le 7 \times 10^5$ $O(n \log^2 n)$，树链剖分+数据结构，各种数据结构嵌套。
$n \le 5 \times 10^6 \sim 10^7$，$O(n \log n)$，堆，map，set，线段树，树状数组，平衡树，主席树，排序+贪心，DP 优化，Trie 树，ACAM，SAM（因为有 $26$ 常数），SA。
$n \le 10^8$，$O(n)$，贪心，双指针，单调队列，单调栈，Hash，KMP。
$n \le 10^{16}$，$O(\sqrt n)$，数论分块，质因数分解。
$n \le 10^{10^6}$，$O(\log n)$，GCD，各种神秘数学。
$n$ 较大，$O(1)$，数学式。