int factorial(int n)
{
if(n < 0) {return -1;}
if(n == 0) {return 1;}
return n*factorial(n-1);
}
私は漸化式再帰アルゴリズムの空間複雑性を見つける一般的な方法は何ですか？時間の複雑さを見つけるために
T(n) = T(n-1) + c = T(n-2) + 2c = ... = T(n-k) + kc => O(n)
T(0) = 1;
を作成する（フィボナッチのような）アルゴリズムのようなもののためのスペースの複雑さを見つけるための一般的な方法は何ですか？コールスタックの深い部分を見つける必要がありますか？
再帰アルゴリズムで必要な領域は、3つの要素で近似できます。スペースを使用すると、階乗の例では、関数に機能
の
T(n) = T(n-1) + cです。展開するときはとなります。だから、再帰スタックにはO(n)のスペースが必要です。 nを保存するには、関数の出力はn!、log（n）ビットが必要です。結果を保存するには、log(n!) = O(n log n)スペースが必要です。
再帰の各ステップで、1つのパラメータ（n）を保存する必要があります。それを保存する必要がありますn回、各パラメータはlog(n)スペースをとります。従って合計でO(nlogn)
あなたはO(n) + O(nlogn) + O(nlogn) = O(nlogn)で終わった。これは、階乗の再帰を計算するために必要なスペースです。この分析を行う
ALPAベータ剪定を行い、正確チェスプログラムが適切な位置を計算するために多くのRAMを必要とする理由、あなたは見つけることができます。
私はあなたの説明を理解しましたが、なぜ誰もが空間の複雑さはO（n）だと言ったのですか？ –
@ivan_petrushenkoは、数字 'n！ 'を保存するのにどれくらいのスペースが必要か尋ねます。小さな数字「n」を5000のように選んでみましょう。彼らはそれが「O（1）」と言うでしょうか？ –
真。 'n'の大きな値に対しては、空間の複雑さは線形ではなく、時間の複雑さにも似ています（私は推測します）.2つの非常に大きな数を掛けることは、' 'return n *階乗（n-1） 'となる。 OPが 'int'を使用しているので、' 19 'より大きい数値を格納することはできないので、私は 'O（n）'を書いています。 – Shubham
この
T（N）= T（N - 1）のような形で時間の複雑さを書き込んだ後+ N
又は
T（N）= 2T（N/2）+ nlogn
など。
次の2つのオプションがあります。
1）あなたは、T（1）またはT（0）されるまでの手順に従った後、合計を計算する必要がありますので、いくつかのケースのためのいくつかの数学の能力を必要とされる繰り返し置換方法を使用します。
または
2）式Master Theoremのようなものであるマスター定理を使用し、多くの実用的な例のために働く
さてあなたは、再帰的にそれをn回呼び出す必要があります、各呼び出しは、上の独自のフレームを割り当てます局所変数と積み重なるので、空間の複雑さはnの次数になります。 – Evk
'factorial'関数を呼び出すたびに、その呼び出しのメモリの「スタック」部分にスタックフレームが作成されます。単一のスタックフレームには、この関数で定義された変数、関数内のパラメータ、および戻りアドレスが含まれます。この場合、すべての呼に対して、この情報を一定時間内に記憶することができる。この関数には呼び出しが線形になるので、合計メモリはO（n）になります。 – Shubham