このアルゴリズム（nまたはlog（n））の空間複雑度はどれくらいですか？

Question

私はスペース（メモリ）に関する質問がある擬似コードのこの特定の部分の複雑さ：

int b(int n, int x) { 
    int sol = x; 
    if (n>1) { 
     for (int i = 1; i <= n; i++) { 
     sol = sol+i; 
     } 
     for (int k=0; k<3; k++) { 
     sol = sol + b(n/3,sol/9); 
     } 
    } 
    return sol; 
} 

コードが呼び出されます：b(n,0)

私の意見は、スペースの複雑さが直線的に進行していること、であるが、それはありますnは、入力としてnが大きくなるため、変数宣言の量も増加します（sol）。

私の友人は、それはlog(n)でなければならないと主張します。私は彼の説明をあまり得ていない。しかし、彼は第2のforループに関する何かを言い、3つの再帰呼び出しが順番に起こることを示しました。

nまたはlog(n)は正しいですか？

Answer 1

（3塩基（n）をログ）数回が呼び出されるbがO(n)れる関数が、空間複雑さO(log(n))であると思います。

プログラムの再帰呼び出しによって、実行スタックが大きくなります。再帰呼び出しが行われるたびに、すべてのローカル変数がスタックにプッシュされます（スタックサイズが増加します）。また、関数が再帰から戻ってくると、ローカル変数がスタックからポップされます（スタックのサイズは小さくなります）。

ここで計算したいのは、実行スタックの最大サイズです。これは、最大再帰深度であり、明らかにO(log(n))です。

Answer 2

Iは、複雑さが

O