时间复杂度
-
O(1)
-
O(n)
-
O(log n):
for(int i=k;i<=n;i+=k) -
O(log log n):
（ps.这个好像不太对哦。for(int i=k;i<=n;i+=k)for(int j=k;j<=k;j+=l)``` -
O(n log log n)：典型代表是线性筛素数算法
tips:
\( \log \log n !=\log^2 n\\ \log^2 n=\log n\times \log n \)
邻接矩阵
查询是否存在某条边:\(O(1)\)。
遍历一个点的所有出边:\(O(n)\)。
遍历整张图:\(O(n^2)\)
空间复杂度:\(O(n^2)\)
邻接表 vector
遍历整张图:O(n+m)。
空间复杂度:O(m)。
链式前向星
遍历整张图:O(n+m)。
空间复杂度:O(m)。
DFS
时间复杂度为 O(n+m)
空间复杂度为 O(n)，
BFS
时间复杂度 O(n+m)
空间复杂度 O(n)(vis 数组和队列)
倍增LCA
倍增算法的预处理时间复杂度为 O(n log n)，单次查询时间复杂度为 O(log n)。
树链剖分
预处理时间复杂度为 O(n)，单次查询时间复杂度为 O(log n)。
拓扑
时间复杂度 O(E+V)
Floyd
时间复杂度:\(O(n^3)\)
空间复杂度:\(O(n^2)\)
dij
时间 O(m log n)
tarjan
时间复杂度 O(n + m)