Chapter 7 时空复杂度分析¶
根据复杂度猜算法类别¶
一般ACM或者笔试题的时间限制是1秒或2秒
在这种情况下，C++代码中的操作次数控制在 \(10^7 \sim 10^8\) 为最佳
下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择:
- \(n \le 30\), 指数级别, dfs+剪枝，状态压缩dp
- \(n \le 100 \Rightarrow O(n^3)\), floyd, dp, 高斯消元
- \(n \le 1000 \Rightarrow O(n^2)\), \(O(n^2 \log n)\), dp, 二分, 朴素版Dijkstra、朴素版Prim、Bellman-Ford
- \(n \le 10000 \Rightarrow O(n * \sqrt{n})\), 块状链表、分块、莫队
- \(n \le 100000 \Rightarrow O(n \log n) \Rightarrow\) 各种sort, 线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
- \(n \le 1000000 \Rightarrow O(n)\), 以及常数较小的 \(O(n \log n)\) 算法 \(\Rightarrow\) 单调队列、hash、双指针扫描、BFS、并查集, kmp、AC自动机，常数比较小的 \(O(n \log n)\) 的做法: sort、树状数组、heap、dijkstra、spfa
- \(n \le 10000000 \Rightarrow O(n)\), 双指针扫描、kmp、AC自动机、线性筛素数
- \(n \le 10^9 \Rightarrow O(\sqrt{n})\), 判断质数
- \(n \le 10^{18} \Rightarrow O(\log n)\), 最大公约数，快速幂，数位DP
- \(n \le 10^{1000} \Rightarrow O((\log n)^2)\), 高精度加减乘除
- \(n \le 10^{100000} \Rightarrow O(\log k \times \log \log k)\), k表示位数, 高精度加减、FFT / NTT
代码分析时间复杂度¶
- 查找，插入，删除：
- 数组：查找 \(O(1)\)，插入删除 \(O(n)\)
- 链表：查找 \(O(n)\)，插入删除 \(O(1)\)
- 哈希表：平均的循环增加法，最差的循环用乘法
- 遍历 & 查找：
- 二叉树可以看"主定理"
- 常见算法分析
- 基础算法
- 快速排序 & 归并排序：每一层复杂度是 \(O(n)\)，一共有 \(\log n\) 层
- 二分 \(O(\log n)\)
- 高精度一层循环，\(O(n)\)
- 双指针：看约束要循环，但内层循环的指针是单向进行的，最多操作 \(n\) 次，因此整体的复杂度是 \(O(n)\)
- 数据结构
- 单链表：插入和删除都是 \(O(1)\)
- 栈与队列的操作都是 \(O(1)\)
- 单调栈和单调队列：每个元素都只会进一次、出一次，复杂度是 \(O(n)\)
- KMP:内层嵌套了一个循环
while(ne[i])，但由于外层每次循环只执行一次j++，因此j最多加 \(n\) 次。 内层循环让j减少，总共最多也只能执行 \(n\) 次，因此算法整体复杂度是 \(O(n)\) - Trie树：时间复杂度与字符串长度呈线性关系
- 并查集：加上路径压缩，最坏是 \(O(n \log n)\)，但路径压缩对数据结构进行了优化，因此实际运行效率更快；再 加上按秩合并可以到 \(O(n \log \alpha(n))\)
- 堆：取堆顶元素，时间复杂度是 \(O(1)\);
up&down操作与堆高度成正比，是 \(O(\log n)\) - 哈希表：理论效率都是 \(O(1)\)，不用考虑最坏情况
- 搜索 & 图论
- dfs树的结构, 最内一层有 \(n!\) 个点，循环一次输出答案；倒数第二层有 \((n-1)!\) 个点，循环一次进行遍历；其他 层同倒数第二层。因此时间复杂度是每一层的复杂度之和。由于 \(n!\) 相比于 \((n-1)!\) 是无穷大量，因此时间复杂 度为 \(O(n! \times n)\)
- 搜索问题都可以画出树来分析
- 图的遍历：有两种，所以每个点只遍历一次，时间是 \(O(n)\)；遍历每个点时都要遍历邻接的边，时间总共是 \(O(m)\)；所以总时间复杂度是 \(O(n+m)\)
- 朴素Dijkstra：两重循环，\(O(n^2)\)
- 堆优化Dijkstra:有列表，只会遍历到所有边一次，每次遍历进行一次堆插入，总时间复杂度是 \(O(m \log m)\)
- Bellman-Ford:两重循环，\(O(nm)\)
- spfa:理论时间复杂度是 \(O(nm)\)，可以被卡，但一般运行时都远快于理论时间复杂度（同样情况的还有匈牙利算 法和最大流算法）求负环就是真正 \(O(nm)\)
- Floyd:三重循环，\(O(n^3)\)
- Prim:两重循环，\(O(n^2)\)
- Kruskal:有一个对边权的排序 \(O(m \log m)\)，平行一个并查集操作 \(O(m)\), 总体复杂度是 \(O(m \log m)\)
- 染色法判断二分图：图的深度或宽度优先遍历，\(O(n+m)\)
- 匈牙利算法：对每一个点循环一次需要 \(O(n)\), 每次判断需要遍历所有点的所有边，因此总共是 \(O(nm)\), 而 \(m\) 最 大等于 \(n^2\), 因此算法复杂度最坏是 \(O(n^3)\), 但实际运行效率非常高
- 数学
- 试除法判定质数 & 分解质因数：\(O(\sqrt{n})\)
- 筛素数：埃氏筛法，两重循环，但内层循环实际是和一个调和级数，因此时间复杂度是 \(O(n \log n)\); 如果再优化成 只让素数去进行内层筛选，则可以优化到 \(O(n \log \log n)\)
- 辗转相除法：\(O(\log n)\) 且常数较小
- 快速幂：\(O(\log k)\), \(k\) 为指数
- 动态规划
- 状态数 = 状态数量 \(\times\) 状态转移的计算量 (计算每个状态需要的计算量)
- 背包问题直接看循环，或者看状态表示的维数
- 完全背包：状态数量 \(nm \times\) 状态转移计算量 \(O(1) = O(nm)\)
- 多重背包：状态数量 \(nV\)(体积) \(\times\) 状态转移计算量 \(O(n) = O(n^2V)\)
- 最长上升子序列的优化：外层循环 \(n\) 次，内层循环 \(\log n\) 次，因此总体是 \(O(n \log n)\)
- 状态压缩DP：看循环，\(O(2^n n)\)
- 树形DP：
- 没有上司的舞会里，把每一条边遍历了一次，\(O(n)\)
- 滑雪：两维，状态数量就是 \(n^2\), 计算每个状态需要循环 4 次，也就是 \(O(1)\)，因此总时间复杂度就是 \(O(n^2)\)
- 贪心：一般是排序 \(O(n \log n)\) + 几重循环