AIAMA 中的DFS复杂度

作者: 苺一語 | 来源:发表于2019-10-30 19:52 被阅读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)$

AIAMA 中的DFS复杂度
《人工智能：一种现代方法》中，给出这样一个复杂度：按照给定条件，树的节点个数最多为：所以容易得出：现在证明：...
LC100 Same Tree
本题链接：Same Tree 本题标签：Tree, DFS 本题难度：方案1：时间复杂度：空间复杂度：
[DFS]90. Subsets II
分类：DFS 时间复杂度: O(n^2) 空间复杂度: O(n^2) 90. Subsets II Given a...
数据结构笔记（图-图的遍历）
深度优先搜索(Depth First Search，DFS)：相当于树的先序遍历用邻接表存储，则DFS的时间复杂度...
[DFS]77. Combinations
分类：DFS 时间复杂度: O(nk)* 77. Combinations Given two integers ...
[DFS]79. Word Search
分类：DFS 时间复杂度: O(mn4^l)** 空间复杂度: O(nn+l)* 79. Word Search ...
[DFS]78. Subsets
分类：DFS 时间复杂度: O(n^2) 78. Subsets Given a set of distinct ...
[DFS]44. Wildcard Matching
分类：DFS/DP 时间复杂度: O(m*n) （两种解法都是这个时间复杂度） 44. Wildcard Matc...
[BackTracking]39. Combination Su
分类：BackTracking/DFS 时间复杂度: O(n^2) 39. Combination Sum Giv...
133. Clone Graph
给无向连通图中节点的引用，返回图的深拷贝。 DFS 对访问过的节点进行标记，然后用dfs 时间复杂度O(n)，空间...

网友评论

本文标题：AIAMA 中的DFS复杂度

本文链接：https://www.haomeiwen.com/subject/qcniiqtx.html

AIAMA 中的DFS复杂度