再帰関数のビッグO表記はどのようにして計算できますか？

Question

私はいくつかの再帰的なメソッドを分析したいが、私はそれを行う方法がわからない。この方法の例は次のとおりです。

public static String tree2prefix(LinkedBinaryTree<String> tree) throws IllegalArgumentException { 

     if (tree == null) { 
      throw new IllegalArgumentException("Tree was null"); 
     } 

     if (!isArithmeticExpression(tree)) { 
      throw new IllegalArgumentException("Tree is not a valid arithmetic expression"); 
     } 

     return tree2prefix(tree.root(), tree); 

    } 

    private static String tree2prefix(Position<String> p, LinkedBinaryTree<String> tree) { 
     if (tree == null) { 
      throw new IllegalArgumentException("Tree was null"); 
     } 

     String prefix = ""; 
     String element = p.getElement(); 
     prefix += element; 

     if (element.equals("+") || element.equals("-") || element.equals("*")) { 
      prefix += " " + tree2prefix(tree.left(p), tree) + " "; 
      prefix += tree2prefix(tree.right(p), tree); 
     } 

     return prefix; 

    } 

誰も私がこのおよび他の同様の方法のための時間を実行している最悪のケースを分析し、見つける方法を理解するのに役立ちます。ありがとう！

編集：

代わり

if (element.equals("+") || element.equals("-") || element.equals("*")) { 
     prefix += " " + tree2prefix(tree.left(p), tree) + " "; 
     prefix += tree2prefix(tree.right(p), tree); 
    } 

のそれがあった：例えば場合

は時間複雑性は異なるだろうあなたが見ることができるようにここで

 prefix += tree2prefix(tree.left(p), tree) + tree2prefix(tree.right(p), tree) 

Answer 1

時間複雑度はO(n)です。最悪の場合の空間の複雑さは、ツリーが歪んでいる場合にはO(n)になります。

なぜO(n)？

ツリーの各ノードをすべてトラバースする必要があるためです。

最悪の場合、なぜ時間複雑度がO(n)になるのですか？

再帰呼び出しは、最大でnオーダーの深度を持つことができます。

ここで、ツリーからプレフィックスへのアルゴリズムの複雑さが考慮されます。