dfs时间复杂度分析

　　之前一直想不明白dfs的时间复杂度是怎么算的，前几天想了下大概想明白了，现在记录一下。

　　存图方式都是链式前向星或邻接矩阵。主要通过几道经典题目来阐述dfs时间复杂度的计算方法。

　　$n$是图中结点的个数，$e$是图中边的个数。

　　时间复杂度为：链式前向星：$O\left( n + e \right)$；邻接矩阵：$O\left( n \right)$

　　给定我们一个图（链式前向星存储），通过深度优先遍历的方式把图中每个结点遍历一遍。

　　首先，图中每个结点最多被遍历一次，这是因为当某个结点被遍历到后，就会对其进行标记，下次再搜索到该结点时就不会再从这个结点进行搜索，所以每个结点最多调用一次dfs函数，所以这里的时间复杂度为$O\left( n \right)$。遍历图的本质是遍历每个结点的邻接结点，也就是说，当从一个结点开始，去遍历其他结点时，都要对该结点的邻接结点遍历一次。因此对于每个结点来说，遍历其邻接结点的时间复杂度为$O\left( e_{i} \right)$，这里的$e_{i}$是指第$i$个结点与其邻接结点相连的边的数量。所以，遍历整一个图的时间复杂度就是把每一个结点进行深度优先遍历的时间复杂度加起来，也就是$O\left( n + e \right)$，即所有结点和所有边的数量。

　　如果图是用邻接矩阵进行存储，则时间复杂度为$O\left( n^{2} \right)$，这是因为每个结点都要对其邻接结点扫描一遍，也就是遍历矩阵的一行，即$O\left( n \right)$，又因为共有$n$个结点，所以时间复杂度就为$O\left( n^{2} \right)$。

　　下面给了深度优先遍历的一个例图。

　　深度优先遍历的代码：

　　以上图为例，这里给出运行的结果：

　　时间复杂度为$O\left( {n \cdot n!} \right)$

　　给定一个数字$n$，求出所有$1 \sim n$的一个全排列。

　　例如求$3$的一个全排列，这里画了个图方面理解（画线的部分是徒手画的，凑合着看吧...）。

　　从$s$出发，第$1$层可以选择$3$个不同的结点，每个结点对应着一个分支。我们先看$s$最左边的那个分支，也就是对应数字$1$的那个分支。第$1$层选择“$1$”这个结点，接着遍历了$3$个邻接结点，对应$3$条边。其中由于$1$已经遍历过了，所有接下来只会从“$2$”和“$3$”开始遍历，而这两个结点都要把其邻接结点都遍历一遍来确定排列的最后一个数字选择哪个。第$1$层的结点“$2$”和“$3$”这两个分支的分析同上。

　　可以发现，每一个结点的邻接结点个数都是$3$，所以循环要执行$3$次来扫描完这$3$个邻接结点。且随着树的深度增加，每层可以选择的结点个数也会随着减小，即深度每增加$1$，该层可选择的结点个数就减$1$（因为上一层已经确定了一个数，每遍历一层都会少一个数的选择）。

　　所以我们来推导更一般的规律，假设求$n$的一个全排列。对应的搜索树大概是这个样子：

　　第$1$层可选择的结点有$n$个。然后对于第$2$层，由于上一层（第$1$层）有$n$个可选择的结点，而每个结点虽然有$n$个邻接结点，但因为在上一层已经确定了一个数，所以实际上下一层（第$2$层）能够选择的结点只有$n - 1$个。又因为上一层有$n$个结点，所以第$2$层可选择的结点个数为$n \cdot \left( n - 1 \right)$(主要是想强调虽然每个邻接结点会被遍历到，但并不是所有的邻接结点都被可以选择去进行下一层的dfs)。同理，在第$3$层中，上一层有$n \cdot \left( n - 1 \right)$个可选择的结点，每个结点实际可选择的邻接结点只有$n - 2$个，故第$3$层可选择的结点个数为$n \cdot \left( n - 1 \right) \cdot \left( n - 2 \right)$。以此类推，到第$n - 1$层，可选择的结点个数为$n \cdot \left( {n - 1} \right) \cdot \left( {n - 2} \right) \cdot ~\cdots~ \cdot 2 = n!$。最后一层不考虑，因为叶子结点没有邻接结点，不会进行遍历邻接结点这个操作。

　　所以时间复杂度就是所有可选择结点遍历其邻接结点的次数。设第$i$层的可选择结点的结点个数为$s_{i}$，每个结点都有$n$个邻接结点，因此所有可选择结点遍历其邻接结点的次数为$$O\left( {n \cdot {\sum\limits_{i = 0}^{n - 1}s_{i}} = n \cdot \left( {1 + n + n \cdot \left( {n - 1} \right) + \cdots + n!} \right)} \right) = O\left( {n \cdot n!} \right)$$

　　补充：我们知道$2^{n} \leq n!$，因此可以将$1 + n + n \cdot \left( {n - 1} \right) + \cdots + n!$进行放缩$$\begin{align*} 1 + n + n \cdot \left( {n - 1} \right) + \cdots + n! &= \frac{n!}{n!} + \frac{n!}{\left( {n - 1} \right)!} + \frac{n!}{\left( {n - 2} \right)!} + \cdots + n! \\ &= n! \cdot \left( {\frac{1}{n!} + \frac{1}{\left( {n - 1} \right)!} + \frac{1}{\left( {n - 2} \right)!} + \cdots + 1} \right) \\ &\leq n! \cdot \left( {\frac{1}{2^{n}} + \frac{1}{2^{n - 1}} + \frac{1}{2^{n - 2}} + \cdots + 1} \right) \\ &\leq n! \cdot 2 \end{align*}$$其中$$\frac{1}{2^{0}} + \frac{1}{2^{1}} + \frac{1}{2^{2}} + \cdots + \frac{1}{2^{n}} = 2 - \frac{1}{2^{n - 1}} < 2$$所以有$$n! \leq 1 + n + n \cdot \left( {n - 1} \right) + \cdots + n! \leq 2 \cdot n!$$$$O\left( {1 + n + n \cdot \left( {n - 1} \right) + \cdots + n!} \right) = O\left( {n!} \right)$$

　　全排列问题的代码：

　　Acwing：https://www.acwing.com/

最后，今天是2022-02-01，祝大家春节快乐！

本文来自博客园，作者：onlyblues，转载请注明原文链接：https://www.cnblogs.com/onlyblues/p/15858616.html