この追加により、DFSの領域と時間の複雑さが保持されますか？

Question

私はノードのツリーの深さの最初の検索を実装しました。各ノードは私が解決している問題の状態をカプセル化しています。また、以下のメソッドを追加して、前のノードですでにチェックした状態をカプセル化するノード。私の質問です：この方法は、アルゴリズムの時間や空間の複雑さをどうにか変えますか、それともDFSO（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（0親が1つのノードのために訪問した）
• レベル2：b.c（1人の親はbルートの子供たちのために訪問した）
• レベル3：2.b^2.c（2人の親がb^2のノードに訪問した）
• ...
• レベルm + 1：m.b^m.c（b^mノード）

総コストC(m)はS(m)が合計であるC(m) = c.S(m)のように書くことができる：

[1]：S(m) = 0 + b + 2.b^2 + ... + m.b^m

だがS(m)の漸近的等価物を見つけよう。 （2）から（1）を引いb.S(m) = 0 + b^2 + 2.b^3 + ... + m.b^(m+1)

います：まずは、

[2]があることを観察しましょう

[3]：(b - 1).S(m) = 0 - b - b^2 - b^3 - ... - b^m + m.b^(m+1)我々は、geometric sumb + b^2 + ... + b^mを識別することができ

簡素化[4]：(b^(m+1) - 1)/(b - 1) - 1。等式の右側のサイズに幾何学的な和を代入

[3] [4]による、その後漸近的優位性を下降することによって用語をグループ化するpとqがmに対して一定である

(b - 1).S(m) = m.b^(m+1) + p.b^m + qが得られます。

m -> +Inf、我々は(b - 1).S(m)〜（相当）m.b^(m+1)を持って、

したがってS(m) ~ [m/(b - 1)].b^(m+1) ~ m.b^m

そのためのコストはそうC(m) = O(m.b^m)C(m) ~ c.m.b^m

に相当します。

はm.b^mので、「支配」b^mはm -> +Infは、あなたのアルゴリズムの全体的な複雑さは、従来のDFSためO(b^m)から、O(m.b^m)なったとき。したがって、時間の複雑さが増す。