登录以参加训练计划

一般试题的时间限制是 1 秒。在这种情况下，C++ 代码中的操作次数控制在 $10^7$ 为最佳。

下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：

• $n \leq 30$, 指数级别,
  • dfs + 剪枝，数字排列，n皇后问题，八数码问题
  • 状态压缩 dp，蒙德里安的梦想，最短 Hamilton 路径
• $n \leq 100$ => $O(n^3)$，
  • floyd，
  • dp，
• $n \leq 1000$ => $O(n^2)$，$O(n^2\log{n})$，
  • dp，
  • 二分，
  • 朴素版 Dijkstra、朴素版 Prim、Bellman-Ford
• $n \leq 10000$ => $O(n\sqrt{n})$，
  • 块状链表、分块、莫队
• $n \leq 100000$ => $O(n\log{n})$ 各种 sort，线段树、树状数组、set/map、heap、dijkstra+heap、prim+heap、spfa、求凸包、求半平面交、二分
• $n \leq 1000000$ => $O(n)$, 以及常数较小的 $O(n\log{n})$ 算法
  • hash、双指针扫描、并查集，kmp、AC 自动机，
  • 常数比较小的 $O(n\log{n})$ 的做法：sort、树状数组、heap、dijkstra、spfa
• $n \leq 10000000$ => $O(n)$，
  • 双指针扫描、kmp、AC 自动机、线性筛素数
• $n \leq 10^9$ => $O(\sqrt{n})$，
  • 判断质数
• $n \leq 10^{18}$ => $O(\log{n})$，
  • 最大公约数，快速幂
• $n \leq 10^{1000}$ => $O((\log{n})^2)$，
  • 高精度加减乘除
• $n \leq 10^{100000}$ => $O(\log{n} \times \log{\log{n}})$，
  • 高精度加减、FFT/NTT

算法时间复杂度分析实例：

一般来说，k重循环，算法时间复杂度就是 $n^k$

基础算法

• 快速排序 归并排序 二分 $O(n\log{n})$
• 双指针 数组元素目标和 $O(n)$

数据结构

• 单链表 栈 (插入 删除操作) $O(1)$
• 单调栈 单调队列 $O(n)$
• KMP $O(n)$
• Trie字符串统计 $O(n)$
• 并查集 (路径压缩) $O(n\log{n})$
• 堆排序 $O(n\log{n})$
• 模拟散列表 $O(1)$

搜索与图论

• 排列数字（全排列） $O(n \cdot n!)$
• dfs bfs $O(n+m)$
• Dijkstra $O(m\log{m})$
• Bellman_ford $O(nm)$
• spfa $O(nm)$
• Floyd $O(n^3)$
• Prim $O(n^2)$
• Kruskal $O(m\log{m})$
• 染色法判定二分图 $O(m\log{m})$
• 匈牙利算法 $O(nm)$
• spfa算法，匈牙利算法，最大流算法时间复杂度理论值很大，但是实际运行速度很快

数学知识

• 试除法判定质数 分解质因数 $\sqrt{n}$
• 筛质数 $n\log{n}$
• 最大公约数 $\log{n}$
• 快速幂 $\log{n}$

动态规划问题的计算量=状态数量*状态转移的计算量

动态规划

• 背包问题 k重循环，算法时间复杂度就是 $n^k$
• 最长上升子序列 II $n\log{n}$
• 蒙德里安的梦想 $2^{2n} \cdot n$
• 没有上司的舞会 $nm$

空间复杂度分析

• 64M = $2^{26}$ Byte
• $2^{26}$ Byte / 4 = $2^{24}$ int = 1.6 * $10^7$ int

注意

• 递归也是需要空间的，递归调用了系统栈，快速排序使用了递归，所以空间复杂度是 $O(\log{n})$
• C++ 中 bool 类型是 1 Byte (8 bits) 长，这是因为 C++ 的数据类型必须是可以通过地址访问的（addressable）。我们无法通过一位创建一个指针，但可以通过一个字节创建一个指针。因此，在 C++ 中，bool 类型的大小是一个字节。敬请期待