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

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

log(10^x)≈3*x

调和级数O(logn)
分母只取质数的调和级数O(loglogn)

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

• $n\le 30$，指数级别
  • dfs+剪枝（排列数字、n皇后、八数码
  • 状态压缩dp（蒙德里安的梦想、最短Hamilton路径
• $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

分析代码时间复杂度：

• 纯循环
• 递归（主定理
  • 归并排序、快速排序：每层O(n)，一共logn层，总复杂度O(nlogn)
• 双指针算法：看起来是两重循环，但内层循环只加不减，最多只走O(n)步，所以总共是O(n)
• 单链表：插入和删除操作O(1)
• 单调栈、单调队列：类似双指针，O(n)
• KMP：看似两层，但外层每增加1时，内层最多增加1，所以O(n)
• Trie字符串：O(n)
• 并查集：路径压缩优化最坏O(nlogn)，一般情况下接近O(n)(？待验证)
• 堆操作：返回堆顶O(1)，down、up操作最坏要经过完全二叉树的所有层O(logn)，用到down、up操作的删除、添加操作就是O(logn)
• hash：最坏情况下很坏但是最坏情况几乎不会出现这一点与快排类似，平均意义上来看增删改查操作时O(1)的
• 图的深度优先遍历和宽度优先遍历：O(n+m)
• dijkstra：朴素O(n^2)，堆优化O(mlogn)
• Bellman-Ford O(n*m)
• SPFA、二分图匈牙利算法、最大流算法都是理论时间复杂度很高但是实际运行效率很快，只要不碰到最坏情况
• SPFA判负环和SPFA求最短路的理论时间复杂度虽然都是O(n*m)，但判负环所需时间比求最短路要高
• prim两重循环O(n^2)
• Kruskal 排序O(mlogm)+并查集操作O(m)=O(mlogm)
• 染色法判断二分图，图的深度优先遍历、宽度优先遍历O(n+m)
• 匈牙利算法最坏O(n*m)，但实际运行非常快
• 试除法，从2循环到sqrt(n),O(sqrt(n))
• 埃氏筛法：虽然是两重循环，但内部循环与n/i有关，总时间复杂度是一个调和级数，结果是O(nlogn)
• 辗转相除法，常数比较小的O(logn)
• 快速幂：k有多少位循环多少次，O(logk)
• 动态规划问题计算量=状态数量*状态转移的计算量
• 贪心：排序+循环
• 查看空间sizeof,单位字节

P.S.

参考y总的由数据范围反推算法复杂度以及算法内容{:target=”_blank”}

参考资料：y总直播，站内卢盼盼笔记