复杂度与算法适用条件速查
公式表常用算法复杂度、前提与实现边界。
关联：全课程
- 符号说明
n,m,V,E,C；O,Theta；dist,dp,l,r
- 使用前提
程序设计、离散数学与数据结构正课。
- 适用范围
本科竞赛与算法训练；先核对输入条件和正确性。
复杂度与算法适用条件速查
| 工具 | 典型复杂度 | 使用前检查 |
|---|---|---|
| 排序 | O(n log n) | 稳定性、比较模型、内存 |
| 二分 | O(log n) | 谓词单调、边界收缩 |
| 双指针 | O(n) | 指针只单调移动 |
| BFS/DFS | O(V+E) | 图表示、判重；BFS为单位权 |
| Dijkstra | O((V+E)logV) | 无负边、距离防溢出 |
| Kruskal | O(ElogE) | 无向图、目标是MST |
| 树上倍增 | O((n+q)logn) | 根、深度和祖先表 |
| 零一背包 | O(nC) | 容量维、倒序、防伪多项式误判 |
| 状压DP | O(2^n n^k) | n足够小、状态充分 |
| KMP | O(n+m) | 失配函数下标约定一致 |
| Dinic | 常用上界O(V²E) | 容量、反向边、守恒 |
任何复杂度都要定义n/m/V/E/C；最坏、平均、期望、摊还不能混写。long long也可能溢出乘法，中间量必要时用__int128。