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

acwing算法基础之时空复杂度分析

article 2024/9/24 16:29:27

1 基础知识

（一）
由数据范围反推算法。

C++中题目给出的要求时间是1秒或2秒计算出结果，而1秒内C++可以执行 $10^7 \sim 10^8$ 次操作。故需要把时间复杂度控制在 $10^8$ 以内。

给定数目范围 $n$ ，有如下情况，

当 $n\leq 30$ 时，指数级别，可以考虑的算法有：dfs+剪枝，状态压缩dp。
当 $\leq 10^2$ 时，可以接受的最大的时间复杂度为 $O(n^3)$ ，那么可以考虑的算法有：floyd，dp。
当 $n\leq 10^3$ 时，可以接受的最大的时间复杂度为 $O(n^2logn)$ ，那么可以考虑的算法有：dp，二分。
当 $\leq 10^4$ 时，可以接受的最大的时间复杂度为 $O(n\sqrt{n})$ ，那么可以考虑的算法有：块状链表。
当 $n\leq 10^5$ 时，可以接受的最大的时间复杂度为 $O (n l o g n)$ ，那么可以考虑的算法有：排序算法（快速排序、归并排序、堆排序），线段树，树状数组，set/map，heap，dijkstra + heap，spfa，求凸包，求半平面交，二分。
当 $\leq 10^6$ 时，可以接受的最大的时间复杂度为常数较小的 $O (n l o g n)$ ，那么可以考虑的算法有：hash，双指针扫描，kmp，AC自动机，排序算法（快速排序、归并排序、堆排序），树状数组，heap，dijkstra，spfa。
当 $n\leq 10^7$ 时，可以接受的最大的时间复杂度为 $O (n)$ ，那么可以考虑的算法有：双指针扫描，kmp，AC自动机，线性筛素数。
当 $n\leq 10^9$ 时，可以接受的最大的时间复杂度为 $O(\sqrt{n})$ ，那么可以考虑的算法有：判断质数。
当 $n\leq 10^{18}$ 时，可以接受的最大的时间复杂为 $O (l o g n)$ ，那么可以考虑的算法有：最大公约数。