时间复杂度特集

定义法计算时间复杂度

单层循环

O(n)

• 求和符号下面的是i能够取到的值域的集合，前面的1指的是每一次循环进来以后每个基本语句都会执行一次

O(logn)

线性变化嵌套循环

• 从左到右，从外层循环到内层循环写求和公式
• 解的时候从里向外解

内外变量互不干扰

内层循环取决于外层变量

指数变化嵌套循环

• 从外层循环向内层循环去写，最里面是核心语句
• 解的时候从内向外解

外层线性变化，内层指数变化，外层限制内层

• 对内层循环变量j来讲，它是每执行一次，然后进行判断，当它自增一次的时候，count++已经执行了两次

外层指数变化，内层线性变化，外层限制内层

三重循环

线性变化，外层限制内层

个人总结——时间复杂度计算

内外嵌套变量关系循环

• 内外嵌套，写级数
  • 最内层为单次的循环个数，求和符号上方写范围，下方写取值集合

函数调用类

• 递归树

主定理

重点比较

408图论算法复杂度+适用场景（含负权边/负环）

算法 / 存储结构	时间复杂度	空间复杂度	适用场景	说明
邻接矩阵	——	O(V²)	稠密图	查询边是否存在快 O(1)，遍历慢 O(V)
邻接表	——	O(V+E)	稀疏图	遍历快 O(V+E)，查询边是否存在慢 O(deg(v))
十字链表（有向图）	——	O(V+E)	需要同时高效处理出度和入度的有向图	每条边存两次引用
邻接多重表（无向图）	——	O(V+E)	需要避免无向边重复存储	每条边只存一次结点
DFS（邻接表）	O(V+E)	O(V+E)	遍历所有顶点与边；拓扑排序；连通分量；检测环	深度优先搜索
DFS（邻接矩阵）	O(V²)	O(V²)	小规模稠密图遍历	遍历邻接点需扫一行
BFS（邻接表）	O(V+E)	O(V+E)	无权图最短路径；分层遍历；连通分量	队列实现、广度优先搜索
BFS（邻接矩阵）	O(V²)	O(V²)	小规模稠密图遍历
拓扑排序（邻接表）	O(V+E)	O(V+E)	DAG 的线性序；任务调度；编译依赖	常用 Kahn 算法（队列）或 DFS
拓扑排序（邻接矩阵）	O(V²)	O(V²)	小规模稠密图	每次找入度=0 需扫一列
Prim 算法（朴素版，邻接矩阵）	O(V²)	O(V²)	稠密图最小生成树	每次扫描所有顶点选最小边
Prim 算法（堆优化版，邻接表）	O(E log V)	O(V+E)	稀疏图最小生成树	用优先队列维护候选边
Kruskal 算法	O(E log E)≈O(E log V)	O(V+E)	稀疏图最小生成树	边排序 + 并查集
Dijkstra（朴素版，邻接矩阵）	O(V²)	O(V²)	稠密图，单源最短路径（不允许负权边）	每次找最近点 O(V)
Dijkstra（堆优化，邻接表）	O(E log V)	O(V+E)	稀疏图，单源最短路径（不允许负权边）	用堆维护最短距离
Floyd 算法	O(V³)	O(V²)	多源最短路径，小规模稠密图，允许负权边；可检测负环（dist[i][i]<0）	若有负环则无解
Bellman-Ford 算法	O(VE)	O(V+E)	单源最短路径，允许负权边；可检测负环（松弛 V 次后仍变化）	若有负环则无解
SPFA 算法	平均 O(E)，最坏 O(VE)	O(V+E)	单源最短路径，允许负权边；可检测负环（某点入队 ≥ V 次）	若有负环则无解
三元组表（边集数组）	——	O(E)	适合稀疏图；常用于 Bellman-Ford、Kruskal、SPFA	每条边存 (i,j,w)，遍历邻接点效率低

并查集三个阶段的时间复杂度

查找算法时间复杂度表

排序算法时间复杂度表

排序算法	平均时间复杂度	最好时间复杂度	最坏时间复杂度	空间复杂度	稳定性	就地性	适用数据对象	比较次数与初始状态关系	移动次数与初始状态关系	排序趟数与初始状态关系
插入排序	O(n²)	O(n)	O(n²)	O(1)	✔ 稳定	原地	数组/链表	有关	有关	无关
折半插入	O(n²)	O(nlogn)	O(n²)	O(1)	✔ 稳定	原地	数组	无关	有关	无关
希尔排序	O(n^1.3)	O(n log n)	O(n²)	O(1)	✘ 不稳定	原地	数组	有关	有关	无关
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	✔ 稳定	原地	数组/链表	有关	有关	有关
快速排序	O(n log n)	O(n log n)	O(n²)	O(log n)	✘ 不稳定	原地	数组	有关	有关	有关
选择排序	O(n²)	O(n²)	O(n²)	O(1)	✘ 不稳定	原地	数组/链表	无关	有关	无关
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	✘ 不稳定	原地	数组	有关	有关	无关
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	✔ 稳定	非原地	数组/链表	有关	无关	无关
计数排序	O(n+k)	O(n+k)	O(n+k)	O(n+k)	✔ 稳定	非原地	数组	无关	无关	无关
基数排序	O(d(n+r))	O(d(n+r))	O(d(n+r))顺序基数排序O(n + r) 链式基数排序O®		✔ 稳定	非原地	数组	无关	无关	无关
桶排序	O(n+k)	O(n+k)	O(n²)	O(n+k)	✔ 稳定	非原地	数组	无关	无关	无关