AIAMA 中的DFS复杂度

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

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

$\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)$

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

赞1赞

赞赏

手机看全文