アルゴリズムの再帰の分析

Question

これは私のアルゴリズムクラスの古い宿題です。私はこの問題に対する解決策を持っていますが、繰り返し試みても、正しい方向にどのように考えて解決策に到達するのか理解できません。

function h(N) { 
    if (N==1) return 3; 
    else { 
     sum = 1; 
     i = 0; 
     while (i < h(N-1)) 
      sum = sum + i; 
      i = i + 1; 
     return sum; 
    } 
} 

H（N-1）は、whileループで繰り返し呼び出されているので、私によると、whileループは、h（N-1）によって返されるものとして倍のような多くの数を実行する必要があります。それに加えて、whileループの関数呼び出しh（N-1）も何回も起こります。

T（N）= T（N-1）* H（N-1）+ C * H（N-1）+ D

：このように、私によると、私はこのような何かを得る必要がありますh（N-1）への1回の再帰呼び出しがT（N-1）を取るので、T（N-1）* H（N-1） ）、比較が行われるたびに再計算されるので、H（N-1）回と呼ばれます。 （N-1）はwhileループ内のステートメントの実行時間です（whileループはH（N- 1）回。

は、私は私の教授から満足のいく答えが得られませんでしたし、誰かが私がこれを理解するのに役立つことができれば私は幸いです。

ありがとうございました！

Answer 1

これを2つのステップで理解してみてください。最初に、whileループをifに置き換えたこの単純な機能を検討してください。ここで

function g(N) { 
    if (N==1) return 3; 
    else { 
     sum = 1; 
     i = 0; 
     if(i < g(N-1)) 
      sum = sum + i; 
      i = i + 1; 
     return sum; 
    } 
} 

、我々は再発を得る：

G(N) = G(N-1) + O(1) 

これまでのところ、とても良いですか？ここで、g（N）を計算する作業には、より小さな問題g（N-1）に一定量の作業を加えたものが含まれます。

ここで元の関数h（N）に戻りましょう。変化したこと？ここで、h（N）を計算する作業は、部分問題h（N-1）、h（N-1）回を解決することを含む。そして、それぞれの時間（つまりwhileループ）では、一定量の作業を行います。また、h（N）で1回だけ、すなわちwhileループの外で行われる別の一定量の作業がある。そこで、我々は基本的に取得する：

H(N) = H(N - 1) *{H(N - 1) + O(1)} + O(1) 

は、我々は置換T(n) = H(n) + O(1)を行うことによって上記を書き換えることができます。したがって、私たちは次のようになります。

T(N) = H(N - 1) * T(N - 1) + O(1) 

Answer 2

をh（N）を実行していることを想定し、ループの各反復でh（N-1）の値が再計算されます（ほとんどの言語およびほとんどのコンパイラの場合が多い）