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

• ACM或者互联网笔试题的时间限制是1秒或2秒。
• 在这种情况下&＃xff0c;C&＃43;&＃43;代码中的操作次数控制在10710^7107为最佳。

下面给出在不同数据范围下&＃xff0c;代码的时间复杂度和算法该如何选择&＃xff1a;

1. n ≤ 30 &＃61;>指数级别, dfs&＃43;剪枝&＃xff0c;状态压缩dp

2. n ≤100 &＃61;> O(n3n_{}^{3}n3​)&＃xff0c;floyd&＃xff0c;dp

3. n ≤ 1000 &＃61;> O(n2n_{}^{2}n2​)&＃xff0c;O(n2n_{}^{2}n2​logn)&＃xff0c;dp&＃xff0c;二分

4. n ≤ 10000 &＃61;> O(n∗nn\sqrt{n}n

   ​ )&＃xff0c;块状链表

5. n ≤ 10510_{}^{5}105​ &＃61;> O(nlogn) &＃xff0c;各种sort&＃xff0c;线段树、树状数组、set/map、heap、dijkstra&＃43;heap、spfa、求凸包、求半平面交、二分

6. n ≤ 10610_{}^{6}106​ &＃61;>O(n)的做法&＃xff1a;hash、双指针扫描、kmp、AC自动机
   常数小的 O(nlogn)的做法&＃xff1a;sort、树状数组、heap、dijkstra、spfa

7. n ≤ 10710_{}^{7}107​ &＃61;> O(n)&＃xff0c;双指针扫描、kmp、AC自动机、线性筛素数

8. n ≤ 10910_{}^{9}109​ &＃61;> O(n\sqrt{n}n

   ​ )&＃xff1a;判断质数&＃xff0c;O(logn)&＃xff1a;快速幂

9. n ≤ 101810_{}^{18}1018​ &＃61;> O(logn)&＃xff0c;最大公约数&＃xff0c;快速幂

$O(nlogn)$&＃xff1a;

• 堆(优先队列) [1], [2], [3]

• 排序 &＃43; 二分 [1]

• 排序 &＃43; 双指针 [1], [2]

• 二分之最小化最大值/最大化最小值 [1]

O(1), O(n)&＃xff1a;贪心