【初赛】时间复杂度 - Slayer

时间复杂度

• 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)