首页 文章

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

提问于
浏览 次
2

所以我为节点树实现了标准的深度优先搜索，其中每个节点封装了我正在解决的问题的状态，我还添加了下面的方法来检查我是否不会通过扩展节点来重复移动封装了我之前在某个节点中检查过的状态 . 我的问题是：这种方法是否会以某种方式改变算法的时间或空间复杂度，或者它们仍然是典型的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;
    }
java time-complexity depth-first-search space-complexity tree-search

1 回答

  • 1

    Space complexity

    checkForRepeatedMoves 似乎没有生成新的对象分配或堆栈上的调用，因此它应该保持DFS的整体空间复杂性不变 .

    Time complexity

    假设为树的每个节点调用 checkForRepeatedMoves ，并且树在每个级别完全填充（松散地说） .

    让我们调用 c 工作单元来检查与父节点进行比较的节点的状态 . 我们假设 c 是常数 .

    让我们分析树的每个级别的成本，从1（根）到 m .

    • Level 1 ： 0 （0个父节点访问过1个节点）

    • 等级 2 ： b.c （1位父亲访问过 b root的子女）

    • 等级 3 ： 2.b^2.c （2个父母访问了 b^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) .

    从"dominates" m -> +Inf 开始，对于传统的DFS，算法的总体复杂度变为 O(m.b^m) ，从 O(b^m) 开始 . 因此增加了时间复杂度 .

    回复于

相关问题