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

一般题目的时间限制为1s / 2s,在这种情况下C++代码中的操作次数控制在1e7为最佳。
下面给出在不同数据范围下所反推出的对应时间复杂度及算法内容:

  • n≤30 => 指数级别 => dfs+剪枝,状压dp
  • n≤1e2 => O(n^3) => floyd,dp
  • n≤1e3 => O(n^2) / O(n^2logn) => dp,二分
  • n≤1e4 => O(n∗√n) => 块状链表
  • n≤1e5 => O(nlogn) => 各种sort,线段树、树状数组、set/map、heap、dijkstra+heap、spfa、求凸包、求半平面交、二分
  • n≤1e6 => O(n) / 常数较小的 O(nlogn) => hash、双指针扫描、kmp、AC自动机、sort、树状数组、heap、dijkstra、spfa
  • n≤1e7 => O(n) => 双指针扫描、kmp、AC自动机、线性筛素数
  • n≤1e9 => O(√n) => 判断质数
  • n≤1e18 => O(logn) => 最大公约数

转载自AcWing yxc

留下评论