特定の再帰関数の成長順序

Question

次の関数の成長の順序は？

static int counter = 0; 

    static void Example(int n) 
    { 
     if (n == 1) return; 

     for (int i = 0; i < n; i++) 
     { 
      counter++; 
     } 

     Example(n/2); 
    } 

それを解決するために、私は次のことを行っている：

私が最初で終わるために、ループの内部を処分した：私はあったことを分析することにより

static void Example(int n) 
    { 
     if (n == 1) return;    

     counter++; 

     Example(n/2); 
    } 

その方法の成長の順序はnのlog base 2であることが分かりました。

だから私は最終的な答えが2倍の何か他のログベースになると思っています。どうすればそれを理解できますか？

Answer 1

のは、オリジナルと修正機能の両方を見てみましょう。元の機能では、次の作業が完了しています。

• 基本ケースチェックの作業量は一定です。
• O（n）は数字を数え上げる作業です。
• サイズの半分に再帰呼び出しするために必要な作業。

我々は漸化式としてこれを表現できる：

• T（1）= 1
• T（N）= N + T（N/2）

はレッツこれがどのように見えるかを見てください。我々は注目することによってこれを拡張開始できる

T（N）= N + T（N/2）

= N +（N/2 + T（N/4）

= N + N/2 + T（N/4）

= N + N/2 +（N/4 + T（N/8））

= N + N/2 + N/4 + T（n/8）

ここでパターンを見ることができます。我々は、T（N/2）ビットk回を展開すると、我々は= N + N/2 + N/4 + ... + N/2 ^K + T

T（n）を得ます（N/2 ^K）

最終的に、これは^K = 1/2 n個の場合、このような場合、我々は

T（N）= N + N/2を有する停止します+ n/4 + n/8 + ... + 1

これは何と評価されますか？興味深いことに、この和は、合計n + n/2 + n/4 + n/8 + ... = 2nであるため、2n + 1に等しい。したがって、この第1の関数はO（n）である。この結論にはMaster Theoremを使用しても到達できましたが、このアプローチもまた興味深いです。

---

ここで、新しい機能を見てみましょう。これはありません

• 基本ケースチェックの作業量は一定です。
• サイズの半分に再帰呼び出しするために必要な作業。

我々は、この再発を書き込むことができるよう

• T（n）が（1）= 1
• T = 1 + T（N/2）

同じトリックを使用（N）

T = 1 + T（N/2）

01：以前のように、のは、T（n）をアウト展開させ

= 1 + 1 + T（N/4）

= 1 + 1 + 1 + T（N/8）より一般

は、k回を展開した後、我々は得る

T（N）= K + T（N/2 ^K）

これはN/2を停止^{K起こる= 1}、 k = log n（すなわち、lg n）。この場合、我々は

T（n）がLG N + T（1）この場合、LG N + 1

だからT（N）= O（LG n）を==こと得ます。

希望すると便利です。

Answer 2

これで、カウンタがn回追加されます。 各コールnは、1に達するまで半減します。

基本的にループが1で、1に対抗するためのnを追加するので、あなたは、ループを排除し、代わりに

counter+=n; 

を使用することができます。

これは、nが実行するたびにカウンタに加算され、次に1に達するまで2ずつ小さくなることを意味します。そう

N =言う40 カウンタ： 40 - > 60 - > 70 - > 75 - > 77 - > 77 N： 40 - > 20 - > 10 - > 5 - > 2 - > 1.

だけ右方向にプッシュ（カウンター+ = N;重要な部分である）