このコードの領域の複雑さは？

Question

int f(int n) 
{ 
    if (n <= 1) 
    { 
     return 1; 
    } 
    return f(n - 1) + f(n - 1); 
} 

私は、時間の複雑さがO(2^n)であることを知っています。なぜか分かります。

しかし、なぜ空間の複雑さがO(n)であるのかわかりません。 いつもノードはn個しかありませんが、それは私には意味がないと言われました。

Answer 1

第2のf(n-1)は、最初のものが完了するまで実行できません（またその逆も同じです）。最初のコールはn回回帰し、すべてのコールが返されるので、合計でnのスタックフレームがプッシュされます。その後、2回目の呼び出しで同じことが行われます。

したがって、再帰で深度がn以上になることはありません。これは、空間の複雑さに貢献する唯一の要因です。

Answer 2

反復の一方の側が葉に達して戻ってくるまで、経路複雑さはO（n）であり、反復の反対側でも同様のことが起こり、すべての中間ステップで再帰で使用される領域は再帰木の深さのOより大きくなければならない。

Answer 3

指数時間複雑度ツリーを描画し、ツリーのルートからのリーフのパスの長さは線形になります。 この直線パスは、アルゴリズムの空間複雑度です。アルゴリズムは、問題を解決するためにそれらのパスのそれぞれをトラバースしますが、スタックに格納されている再帰呼び出しの最大数はリニアになります。例：f(3)

  3 
    / \ 
    2  2 
    /\ /\ 
    1 1 1 1 

のルートからリーフへの最大長はO(n)あります。従って、空間の複雑さもO(n)である。