次のコードは、空間の複雑さO（N）のみを持つのはなぜですか？

Question

これは、Gayle Lakmaan McDowellによるコーディングインタビューをクラッキングすることから直接得られたものです。

彼女は、次のコードを示しています：

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

彼女は時間の複雑さは、O（2^n）がある理由について明確な説明を持っているのが、なぜここにスペースの複雑さだけでO（N）はありますか？

Answer 1

スペースの複雑さがコールスタックの使用を考慮しています。この関数は、返す前に自身をO(N)回呼び出すので、コールスタックはO(N)深くなります。

更新（おかげ@MatthewWetmore）：

明確にするために、f(n-1) + f(n-1);式中の2つの再帰呼び出しが並列に実行されません。最初の1回の呼び出しは、リニアスタック使用量を消費し、2回目の呼び出しは、同じスタックサイズを消費します。したがって、スペースの倍増は起こっていません。これは実行時間消費とは異なります（各呼び出しが明らかに蓄積されています）。

Answer 2

それが使用しているFのような関数呼び出し のシステムスタックに多くのスペース（5）F（4）Fを呼び出すウィルどの呼ぶ（3）

F（5） - > F（4） - >

このように、F（3）→F（2）→F（1）→戻り値は、F F（n）については、空間はO（N）

Answer 3

となります.O表記は、漸化表記です。これは、アルゴリズムを完了するための時間が決して一定の限界を超えず、それ以下になることがあることを表記していますが、これは指定されていません。 アルゴリズムの時間複雑さは、入力のサイズによって異なります。これは、{1} 1つの数字の入力、または{1,2}の入力で、前の入力のサイズの2倍になります。それはnがO（n）を意味するものです。これは、アルゴリズムが直線的な複雑さを有することを意味し、これはアルゴリズムを完了するための時間がn *一定の定数またはC * nであることを意味する。
Cの正確な値を省略することができる覚醒表記法を使用する理由はC井戸をどのように決定するのか自分自身に問いかけるかもしれませんが、これはアルゴリズムが入力の順序または他の何らかの状態である。複雑さがCnで最悪のシナリオがCnlognであることがわかります。この場合、アルゴリズムはO（nlogn）の複雑さを持っています。これは、最悪のシナリオを境界として取るためです。この場合、Cを省略し、最良のシナリオCnを省略します。コンピュータプログラミングブック1の技術、またはAlgorithms by Robert Sedgewickのような詳細については、アルゴリズムブックを読むことを検討することもできます。 Sedgewickの本はJavaを使い、とてもアクセスしやすいです。

空間の複雑さは同じですが、今度はメモリ空間について言及しています。ダイナミックプログラミングと呼ばれる手法があり、この手法は後でサブプログラムの解決策として使用できます。そうすれば、問題を解決するために必要なメモリの量は、古典的な例が増加するのに、サブ問題に何度も掛かる時間を省略しますが、Change-making problemです。多くのソリューションを保存し、システムメモの増加に必要なスペースを確保します。この問題は、問題を解決するために必要なメモリ量が関数Cnとして動作するため、線形空間の複雑さがあります。

例として、この関数はメモリ内の1つのスペースとも言えるnを使用します.1つの定数は別のものですので、メモリ内のスペースは1 + nになります。この場合、線形関数は変位を有し、線形関数はCn + aであり、C = 1かつa = 1であると言う。線形関数である。再帰が1になるまでn個の数値を格納するためにメモリにn個のスペースが必要なので、nは再帰に由来します。たとえば、n = 3とします。

初めて3回私たちがメモリ2に記憶している最後の1の再帰を下るにつれて、メモリがすでに存在しているかどうかは、1が存在する空間がスタックまたはヒープ上に存在する可能性があるためです。だから私たちはO記法を使うのですが、これはアーキテクチャの実装に依存しています。だから時には複雑さが1 + nになることもありますが、それはnでもかまいませんが、O（n）と言って私たちは両方のケースをカバーします。

また、あなたがラインに疑問がある場合：アーキテクチャに応じて

f(n-1) + f(n-1); 

をあなたはスタックを有していても、あなたはメインメモリに送ることができます（このアーキテクチャのは例が心に来ることはありません）とゴミを持っていますコレクタは範囲外になると参照を消去しますが、3 * 2、2 * 2、1 * 2を格納すると線形スペースになります。この場合、2n + 1または2nになります。まだ線形。しかし、私はあなたがスタックを持っているこのようなものは何も見ていないと思います。再帰が戻るとすぐにスタックからすべての変数をポップし始めます。最大で1 + nまたはn + 1を使います。