この方法を考えると：
int f(int n) {
if (n <= 0) {
return 1;
}
return f(n - 1) + f(n - 1);
}
次のようにスタック呼び出し/バイナリツリーを作成します。
n
/ \
n-1 n-1
/ \ / \
n-2 n-2 n-2 n-2 etc
例えば。n = 3
3
/ \
2 2
/ \ / \
1 1 1 1
/ \ / \ / \ / \
0 0 0 0 0 0 0 0
2 ^（n + 1）-1 => 15ノード/呼び出し。時間計算量はO（2 ^ n）です
私の質問は、なぜ空間の複雑さ= O（h）、hは木の高さを表すのですか？この例では3ですか？言い換えると、各メソッド呼び出しに入力変数nに対して1つのメモリ空間がある場合、すべてのメソッド呼び出しに対して1つのメモリ空間があると言えます。O（2 ^ n）メソッド呼び出しがある場合、スペースがO（2 ^ n）と等しくないのはなぜですか？私の参照では、「常にO（N）のみが存在する」と書かれていますが、これは私には意味がありませんでした。
スタックフレームは、メソッド呼び出し、そのパラメーターと変数、および呼び出し元の戻りアドレスを表すものと考えています。これが私の混乱の根源かもしれません。
これは並行/並列アルゴリズムではないため、関数の出力を計算するために発生するステップの最終的な視覚化は同時ではないことに注意することが重要です。
このようにアルゴリズムを書き直すと、より明白になる可能性があります。
int f(int n) {
if (n <= 0) {
return 1;
}
int temp1 = f(n - 1);
int temp2 = f(n - 1);
return temp1 + temp2;
}
したがって、最初f(n - 1)と2番目の呼び出しはf(n - 1)同時に発生しません。
つまり、任意の時点で、次のような線形呼び出しスタックがあります。
f(3)
/
f(2)
/
f(1)
/
f(0)
この時点で、サイズ4の呼び出しスタックがあります。f(0)が計算されると、最後の要素要素がスタックからポップされ、サイズ3の呼び出しスタックが作成されます。
f(3)
/
f(2)
/
f(1)
この時点で、アルゴリズムはf(1)（の右側のサブツリーf(1)）への2番目の呼び出しを評価します。
f(3)
/
f(2)
/
f(1)
\
f(0)
サイズ4のコールスタックが再びあります。次のいくつかのステップで、コールスタックは次のように変換されます。
f(3)
/
f(2)
/
f(1)
その後：
f(3)
/
f(2)
その後：
f(3)
/
f(2)
\
f(1)
その後：
f(3)
/
f(2)
\
f(1)
/
f(0)
その後：
f(3)
/
f(2)
\
f(1)
その後：
f(3)
/
f(2)
\
f(1)
\
f(0)
このプロセスは、アルゴリズムが終了するまで続きます。
したがって、アルゴリズムの空間の複雑さはO（h）であると結論付けることができます。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加