当前位置：首页 > news >正文

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

news 2025/8/15 4:48:31

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

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

$n\leq30$ ，指数级别， $df s +$ 剪枝，状态压缩 $d p$ ；
$n\leq100\rArr O(n^3)$ ， $f l oy d$ ， $d p$ ，高斯消元；
$n\leq1000\rArr O(n^2)$ ， $O(n^2logn)$ ， $d p$ ，二分，朴素版 $D ijk s t r a$ ，朴素版 $P r im$ ， $B e ll man - F or d$ ；
$n\leq10000\rArr O(n*\sqrt{x})$ ，块状链表、分块、莫队；
$n\leq100000\rArr O(nlogn)\rArr$ ，各种 $sor t$ ，线段树、树状数组、 $se t / ma p$ 、 $h e a p$ 、拓扑排序、 $d ijk s t r a + h e a p$ 、 $p r im + h e a p$ 、 $Kr u s ka l$ 、 $s p f a$ 、求凸包、求半平面交、二分、 $C D Q$ 分治、整体二分、后缀数组、树链剖分、动态树；
$n\leq1000000\rArr O(n)$ ，以及常数较小的 $O (n l o g n)$ 算法 $\rArr$ 单调队列、 $ha s h$ 、双指针扫描、 $BFS$ 、并查集、 $km p$ 、 $A C$ 自动机，常数比较小的 $O (n l o g n)$ 的做法： $sor t$ 、树状数组、 $h e a p$ 、 $d ijk s t r a$ 、 $s p f a$ ；
$n\leq10000000\rArr O(n)$ ，双指针扫描、 $km p$ 、 $A C$ 自动机、线性筛素数；
$n\leq10^9\rArr O(\sqrt{n})$ ，判断质数；
$n\leq10^{18}\rArr O(logn)$ ，最大公约数，快速幂，数位DP；
$n\leq10^{1000}\rArr O((logn)^2)$ ，高精度加减乘除；
$n\leq10^{100000}\rArr O(logk\times loglogk)$ ， $k$ 表示位数，高精度加减， $FFT / NTT$ 。