4

次のC関数について考えてみます。

double foo (int n) {
    int i;
    double sum;
    if (n==0)
        return 1.0;
    else {
        sum = 0.0;
        for (i=0; i<n; i++)
        sum +=foo(i);
        return sum;
    }
}

上記の関数のスペースの複雑さは次のとおりです。

（a）O（1）（b）O（n）（c）O（n！）（d）O（n ^ n）

私が行ったことは、上記のコードの漸化式を計算することですが、それでもその漸化式を解決することはできません。これは在宅勤務関連のサイトではないことを私は知っています。しかし、どんな助けもいただければ幸いです。

これが私の再発です。

T（n）= T（n-1）+ T（n-2）+ T（n-3）+ T（n-4）+ ........ + T（1）+ S

ここで、Sは定数です。

4

4 に答える 4

4

それは、スタックについて話しているのか、ヒープスペースの複雑さについて話しているのかによって異なります。

ヒープの場合、O(1)またはO(0)ヒープメモリを使用していないためです。（基本的なシステム/プログラムのオーバーヘッドは別として）

スタックの場合、それはO(n)です。これは、再帰がNレベルを深くするためです。

最も深いポイントは次のとおりです。

foo(n)
    foo(n - 1)
        foo(n - 2)

        ...

        foo(0)
于 2011-12-23T19:04:35.817 に答える
2

スペースの複雑さは、プログラムに必要なスペースの量を表します。fooは配列を宣言しないため、各レベルにはスペースが必要ですO(1)。ここで行う必要があるのは、任意の時点で最大でアクティブにできるネストされたレベルの数を把握することだけです。

編集：...あなたが自分で解決策を理解できるようにするためにたくさん:)

于 2011-12-23T19:05:24.200 に答える
1

漸化式をどのように導き出したのか説明していません。私はこのようにします：

  1. n == 0の場合、foo一定のスペースを使用します（再帰はありません）。
  2. n> 1の場合foo、0からn-1（両端を含む）までのiごとに1回繰り返します。再帰ごとに、（呼び出し自体に）一定のスペースと再帰呼び出しにT（i）スペースを使用します。しかし、これらの呼び出しは次々に発生します。各呼び出しで使用されるスペースは、次の呼び出しの前に解放されます。したがって、それらを追加するのではなく、単に最大値を追加する必要があります。Tは減少しないため、これはT（n-1）になります。
于 2011-12-23T19:05:45.287 に答える
1

空間の複雑さはO（n）になります。あなたが言ったように、それはO（n * n）のように見えるかもしれませんが、ループでsay（i = 1）の呼び出しが行われると、これのためにスタックで使用されたスペースが削除されることを覚えておく必要があります。したがって、i = n-1の場合、最悪のケースを考慮する必要があります。次に、再帰関数呼び出しの最大数が同時にスタックに存在します

于 2011-12-24T17:38:40.370 に答える