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)$
  • floyd
  • dp
• $n \le 1000$，$O(n^2)$，$O(n^2 \log n)$
  • dp
  • 二分
  • 朴素版Dijkstra
  • 朴素版Prim
  • Bellman-Ford
• $n \le 10000$，$O(n\sqrt{n})$
  • 块状链表
  • 分块
  • 莫队
• $n \le 10^5$，$O(n\log n)$
  • 各种排序算法
  • 线段树
  • 树状数组
  • set/map
  • heap
  • 拓扑排序
  • 堆优化Dijkstra
  • 堆优化Prim
  • SPFA
  • 求凸包
  • 求半平面交
  • 二分
• $n \le 10^6$
  • $O(n)$
    • Hash
    • 双指针扫描
    • 并查集
    • KMP
    • AC自动机
  • 常数较小的$O(n\log n)$
    • 排序
    • 树状数组
    • heap
    • Dijkstra
    • SPFA
• $n \le 10^7$，$O(n)$
  • 双指针扫描
  • KMP
  • AC自动机
  • 线性筛素数
• $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总的由数据范围反推算法复杂度以及算法内容{:target=”_blank”}