此添加是否保留了 DFS 的 space 和时间复杂度?
Does this addition preserve the space and time complexity for DFS?
所以我实现了节点树的标准深度优先搜索,其中每个节点封装了我正在解决的问题的状态,我还添加了下面的方法来检查我不会重复移动通过展开一个节点,该节点封装了我已经在某个先前节点中检查过的状态。我的问题是:这种方法是否会以某种方式改变算法的时间或 space 复杂性,或者它们仍然分别是 DFS O(b^m) 和 O(bm) 的典型方法(这里 b - 分支因子和m - 最大深度)。
//additional method which prevents us from repeating moves
public boolean checkForRepeatedMoves(Node node) {
Node nodeBeingChecked = node;
//if the current node's state is the same as the state of its parent or its parent's parent and so on.. then we are repeating a move
while (node.getParent() != null) {
if(node.getParent().getState().isEqualTo(nodeBeingChecked.getState())) {
return true;
}
node = node.getParent();
}
//if we have reached the root and no repetition is detected - return false
return false;
}
Space复杂度
checkForRepeatedMoves
似乎不会生成新的 object 分配或对堆栈上的 pile-up 调用,因此它应该保持 DFS 的总体 space 复杂性不变.
时间复杂度
让我们假设 checkForRepeatedMoves
为树的每个节点调用,并且树在每个级别都完全填充(松散地说)。
让我们调用 c
工作单元来检查与 parent 节点进行比较的节点的状态。假设 c
是常量。
让我们细分树的每个级别的成本,从 1(根)向下到 m
。
- 级别
1
:0
(0 parent 访问了 1 个节点)
- 级别
2
:b.c
(b
root 的 children 访问了 1 parent)
- 级别
3
:2.b^2.c
(b^2
个节点访问了 2 parent 秒)
- ...
- 级别
m + 1
:m.b^m.c
(parent 秒访问了 b^m
个节点)
总成本 C(m)
可以写成 C(m) = c.S(m)
其中 S(m)
是总和:
[1]: S(m) = 0 + b + 2.b^2 + ... + m.b^m
让我们找到 S(m)
的渐近等价物。首先,让我们观察一下
[2]: b.S(m) = 0 + b^2 + 2.b^3 + ... + m.b^(m+1)
从 (2) 中减去 (1) 得出:
[3]: (b - 1).S(m) = 0 - b - b^2 - b^3 - ... - b^m + m.b^(m+1)
在哪里我们可以识别 geometric sum b + b^2 + ... + b^m
,它简化为 [4]:(b^(m+1) - 1) / (b - 1) - 1
.
用 [4] 代替等式 [3] 的 right-hand 大小的几何和,然后按递减渐近优势对项进行分组得到
(b - 1).S(m) = m.b^(m+1) + p.b^m + q
其中 p
和 q
相对于 m
是常数。
当m -> +Inf
时,我们有(b - 1).S(m)
~(相当于)m.b^(m+1)
,
因此S(m) ~ [m/(b - 1)].b^(m+1) ~ m.b^m
因此成本相当于C(m) ~ c.m.b^m
所以C(m) = O(m.b^m)
.
由于 m.b^m
"dominates" b^m
当 m -> +Inf
时,你的算法的整体复杂度从 O(b^m)
变为 O(m.b^m)
DFS。时间复杂度因此增加。
所以我实现了节点树的标准深度优先搜索,其中每个节点封装了我正在解决的问题的状态,我还添加了下面的方法来检查我不会重复移动通过展开一个节点,该节点封装了我已经在某个先前节点中检查过的状态。我的问题是:这种方法是否会以某种方式改变算法的时间或 space 复杂性,或者它们仍然分别是 DFS O(b^m) 和 O(bm) 的典型方法(这里 b - 分支因子和m - 最大深度)。
//additional method which prevents us from repeating moves
public boolean checkForRepeatedMoves(Node node) {
Node nodeBeingChecked = node;
//if the current node's state is the same as the state of its parent or its parent's parent and so on.. then we are repeating a move
while (node.getParent() != null) {
if(node.getParent().getState().isEqualTo(nodeBeingChecked.getState())) {
return true;
}
node = node.getParent();
}
//if we have reached the root and no repetition is detected - return false
return false;
}
Space复杂度
checkForRepeatedMoves
似乎不会生成新的 object 分配或对堆栈上的 pile-up 调用,因此它应该保持 DFS 的总体 space 复杂性不变.
时间复杂度
让我们假设 checkForRepeatedMoves
为树的每个节点调用,并且树在每个级别都完全填充(松散地说)。
让我们调用 c
工作单元来检查与 parent 节点进行比较的节点的状态。假设 c
是常量。
让我们细分树的每个级别的成本,从 1(根)向下到 m
。
- 级别
1
:0
(0 parent 访问了 1 个节点) - 级别
2
:b.c
(b
root 的 children 访问了 1 parent) - 级别
3
:2.b^2.c
(b^2
个节点访问了 2 parent 秒) - ...
- 级别
m + 1
:m.b^m.c
(parent 秒访问了b^m
个节点)
总成本 C(m)
可以写成 C(m) = c.S(m)
其中 S(m)
是总和:
[1]: S(m) = 0 + b + 2.b^2 + ... + m.b^m
让我们找到 S(m)
的渐近等价物。首先,让我们观察一下
[2]: b.S(m) = 0 + b^2 + 2.b^3 + ... + m.b^(m+1)
从 (2) 中减去 (1) 得出:
[3]: (b - 1).S(m) = 0 - b - b^2 - b^3 - ... - b^m + m.b^(m+1)
在哪里我们可以识别 geometric sum b + b^2 + ... + b^m
,它简化为 [4]:(b^(m+1) - 1) / (b - 1) - 1
.
用 [4] 代替等式 [3] 的 right-hand 大小的几何和,然后按递减渐近优势对项进行分组得到
(b - 1).S(m) = m.b^(m+1) + p.b^m + q
其中 p
和 q
相对于 m
是常数。
当m -> +Inf
时,我们有(b - 1).S(m)
~(相当于)m.b^(m+1)
,
因此S(m) ~ [m/(b - 1)].b^(m+1) ~ m.b^m
因此成本相当于C(m) ~ c.m.b^m
所以C(m) = O(m.b^m)
.
由于 m.b^m
"dominates" b^m
当 m -> +Inf
时,你的算法的整体复杂度从 O(b^m)
变为 O(m.b^m)
DFS。时间复杂度因此增加。