ビッグO再帰関数の表記

Question

私は大きなO表記を練習していましたが、再帰関数を除いてはわかりました。私は単純なものに対処することができます（O(n)またはO(1)のようなものですが、他の何かが失われてしまうもの） 以下は3つの練習問題です。回答者がどのように答えを見つけたか説明していただければ幸いです。

あなたが method2の n電話を持つことになりますので、

public static int method2(int n) 
    { 
    if (n < 1) throw new IllegalArgumentException(); 
    if (n == 1) 
     return 2; 
    else 
     return method2(n - 1) * (2 * n); 
    } 


    public static void method3(int n) 
    { 
    if (n < 1) throw new IllegalArgumentException(); 
    if (n == 1) 
     System.out.print("1"); 
    else { 
     method3(n - 1); 
     System.out.print(", " + n); 
    } 
    } 


    public static void method4(int n) 
    { 
    if (n < 1) throw new IllegalArgumentException(); 
    if (n==1) System.out.print(1); 
    else if (n==2) System.out.print("1 1"); 
    else { 
     System.out.print((n+1)/2+ " "); 
     method4(n-2); 
     System.out.print(" "+(n+1)/2); 
    } 
} 
} 

Answer 1

この例では。あなたがnで始まり、それが1に来るまで1で下る、method2で

。非常に簡単であり、それがO(n)です。

method3はmethod2と同じですが、操作がまったく異なります。 nを1に減らすことによって、その1までmethod3に電話をします。 で

あなたはその1または2まで、2によってnを減らすので、あなたはまだO（n）がn/2の手順を、行います。

これは、再帰関数の速度を理解するための最良の例ではありません。あなたは再帰のための複数のオプションを持つサンプルで遊ぶ必要があります。

これらすべてのオプションは、同じ複雑さを持つforループに変換することができます。そのようにすれば、それがあなたを助けることができる場合は、そのように考えてみてください。