Acwing《算法基础课》第7章 时空复杂度分析

文章目录

Acwing《算法基础课》第7章 时空复杂度分析

---

一般ACM或者笔试题的时间限制是$1$秒或$2$秒

C++一般$1$s能计算$10^7$~$10^8$次，在这种情况下，C++代码中的操作次数控制在 $10^7$为最佳

在不同数据范围下，代码的时间复杂度和算法的选择技巧如下：

$n\le 30$，指数级别 dfs+剪枝状态压缩dp $n\le 100$，$O(n^3)$ floyddp $n\le 1000$，$O(n^2)$，$O(n^2\log n)$ dp二分朴素版Dijkstra朴素版PrimBellman-Ford $n\le 10000$，$O(n\sqrt{n})$ 块状链表分块莫队 $n\le 10^5$，$O(n\log n)$ 各种排序算法线段树树状数组set/mapheap拓扑排序堆优化Dijkstra堆优化PrimSPFA求凸包求半平面交二分 $n\le 10^6$ $O(n)$ Hash双指针扫描并查集KMPAC自动机 常数较小的$O(n\log n)$ 排序树状数组heapDijkstraSPFA $n\le 10^7$，$O(n)$ 双指针扫描KMPAC自动机线性筛素数 $n\le 10^9$，$O(\sqrt{n})$ 判断质数 $n\le 10^{18}$，$O(\log n)$ 最大公约数快速幂 $n\le 10^{1000}$，$O((\log n{)}^2)$ 高精度加减乘除 $n\le 10^{100000}$，$O(\log n\times \log \log n)$ 高精度加减FFT/NTT

小技巧

${\log }_{2}10^n=3n$64MB至多开1600万个int

---

P.S. 部分内容来自y总的由数据范围反推算法复杂度以及算法内容 如果大家有兴趣，可以去Acwing《算法基础课》看看 我在Acwing也分享了一份，欢迎去围观