算法备忘录·时空复杂度分析

一直以来，没能系统学习算法，是我心中的痛；现在学了 y 总的算法基础课，做做笔记，希望能够有所收获。
这是第八节，时空复杂度分析。

时空复杂度分析

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

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

• $n\leq 30$，指数级别

  • dfs + 剪枝
  • 状态压缩 DP

• $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
  • Kruskal
  • spfa
  • 求凸包
  • 求半平面交
  • 二分
  • CDQ分治
  • 整体二分
  • 后缀数组
  • 树链剖分
  • 动态树

• $n\leq 1000000$，$O(n)$、常数比较小的 $O(nlog n)$

  • 单调队列
  • hash
  • 双指针扫描
  • 并查集
  • kmp
  • AC自动机
  • 【常数比较小的 $O(nlogn)$ 的做法】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)$

  • 最大公约数
  • 快速幂
  • 数位 DP

• $n\leq 10^{1000}$，$O((\log n)^2)$

  • 高精度加减乘除

• $n\leq 10^{100000}$，$O(\log k \times \log\log k)$，$k$ 表示位数

  • 高精度加减
  • FFT/NTT

求时间复杂度

• 循环
• 递归：主定理（并不实用）
• 动态规划：状态数量 * 状态转移的计算量

• 小技巧
  • $\log_2 10^n\approx 3n$
  • 自然数的倒数和的增长速度是 $O(\log n)$
  • 质数的倒数和的增长速度是 $O(\log \log n)$

求空间复杂度

• 64MB 至多开 1600 万个 int

---

算法备忘录系列目录：
第一节 算法备忘录·基础算法
第二节 算法备忘录·数据结构
第三节 算法备忘录·STL
第四节 算法备忘录·搜索与图论
第五节 算法备忘录·数学知识
第六节 算法备忘录·动态规划
第七节 算法备忘录·贪心
第八节 算法备忘录·时空复杂度分析