AIAMA 中的DFS复杂度

2019-10-30 本文已影响0人苺一語

《人工智能：一种现代方法》中，给出这样一个复杂度：

按照给定条件，树的节点个数最多为：

$\frac{1-b^m }{1-b}$

所以容易得出：

$T(m,b)=O(\frac{1-b^m}{1-b} )$

现在证明：存在 $n\in N^*$ ，使得当 $\frac{1-b^m }{1-b} >n$ 时，有 $b^m>\frac{1-b^m }{1-b}$ ：

不等式变形：

$b^m>\frac{1-b^m }{1-b}$

$\Leftrightarrow b^m(1-b)>1-b^m$

$\Leftrightarrow b^m-b^{m+1}>1-b^m$

$\Leftrightarrow 2b^m-b^{m+1}>1$

不妨取 $\begin{cases} b=1.5 \\ m=2 \end{cases}$ 为不等式的一个解，

此时 $\frac{1-b^m }{1-b}=2.5$

故可取 $n=3$ ，得证。

又根据大O表示法的定义：

可得： $T(m,b)=O(b^m)$