此添加是否保留了 DFS 的 space 和时间复杂度？

Question

所以我实现了节点树的标准深度优先搜索，其中每个节点封装了我正在解决的问题的状态，我还添加了下面的方法来检查我不会重复移动通过展开一个节点，该节点封装了我已经在某个先前节点中检查过的状态。我的问题是：这种方法是否会以某种方式改变算法的时间或 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;
    }

Answer 1

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。时间复杂度因此增加。

此添加是否保留了 DFS 的 space 和时间复杂度？

Does this addition preserve the space and time complexity for DFS?

java

time-complexity

depth-first-search

space-complexity

tree-search