常见数据规模 (n) 可接受的时间复杂度 常见算法举例
n ≤ 20 O(2ⁿ), O(n!) 深度优先搜索 (DFS)、状态压缩动态规划
n ≤ 1,000 O(n²), O(n² log n) 动态规划、Floyd算法、朴素Dijkstra
n ≤ 100,000 O(n log n) 排序、线段树、树状数组、堆、分治、最短路算法
n ≤ 1,000,000 O(n) 单调栈、KMP、并查集（路径压缩）、双指针、哈希表
n > 1,000,000 O(1), O(log n) 数学公式、二分查找、快速幂

图常用算法

搜索算法

深度优先搜索

广度优先搜索

最短路径算法

Dijkstra

  • 解决非负权图的单源最短路径问题，使用贪心策略

Bellman-Ford

  • 处理含负权边的图的单源最短路径，并能检测负权环

Floyd-Warshall

  • 计算所有顶点对的最短路径，适用稠密图

最小生成树算法

Kruskal

  • 按权重从小到大选择边，使用并查集检测环，适合稀疏图

Prim

  • 从起点逐步扩展最小生成树，使用优先队列，适合稠密图

拓扑排序算法

  • 针对有向无环图的顶点进行线性排序，使得对每条边(u,v)，u在v前