java - 这种添加是否保留了 DFS 的空间和时间复杂度？

Question

因此，我实现了标准深度优先搜索节点树，其中每个节点封装了我正在解决的问题的状态，并且我还添加了下面的方法来检查我不会通过扩展来重复移动一个节点，它封装了我已经在某个先前节点中检查过的状态。我的问题是:这种方法是否以某种方式改变了算法的时间或空间复杂度，或者它们仍然分别是 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

空间复杂度

checkForRepeatedMoves 似乎不会生成新的对象分配或在堆栈上堆积调用，因此它应该使 DFS 的整体空间复杂度保持不变。

时间复杂度

假设树的每个节点都调用了 checkForRepeatedMoves，并且树在每个级别都已完全填充(宽松地说)。

让我们将 c 称为工作单元，以执行与父节点进行比较的节点状态的检查。我们假设 c 是常数。

让我们对树的每一层的成本进行分割，从 1(根)到 m。

• 级别 1 :0(1 个节点访问了 0 个父节点)
• 级别2:b.c(b根的子级访问了1个父级)
• 级别3:2.b^2.c(为b^2节点访问了2个父级)
• ...
• 级别 m + 1 :m.b^m.c(m 个父级访问了 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] 右侧大小中的几何和，然后按递减渐近优势对项进行分组，得出

(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 -> +Inf 时，m.b^m “主导”b^m，因此算法的整体复杂度变为 O(m.b^m)，来自传统 DFS 的 O(b^m)。时间复杂度因此增加。