0

次の2つのケースで、時間と空間の複雑さに関連する疑問があります

引用符

ケース I:

Recurion: 階乗計算。

int fact(int n)
{
    if(n==0)
      return 1;
    else
      return (n*fact(n-1));
}

ここで、なぜ時間の複雑さが 2*n になり、空間の複雑さが n に比例するのでしょうか。

と

ケース II:

反復:-

int fact(int n)
{
    int i, result = 1;
    if(n==0)
    result = 1;
    else
         {
           for(1=1;i<=n;i++)
              result*=i;
         }
     return (result);
}

時間の複雑さは n に比例し、空間の複雑さは一定です。これはいつも私を混乱させます。

4

3 に答える 3

1

私の推論が間違っている場合は、誰かが私を修正してください:)

スペースの複雑さについては、次のように説明します。

再帰的なソリューションでは、n再帰的な呼び出しがあるため、nスタックが使用されます。コールごとに 1 つ。したがって、O(n)スペース。これは、反復ソリューションの場合には当てはまりません。スタックは 1 つだけで、配列も使用していません。変数は 1 つしかありません。したがって、空間の複雑さはO(1)です。

反復解の時間計算量については、ループ内にn乗算があるため、緩い境界は になります。他のすべての操作は、アルゴリズムの全体的な効率に関係なく、単位時間または定数時間であると想定できます。再帰的な解決策については、よくわかりません。各ステップで 2 つの再帰呼び出しがある場合、呼び出しスタック全体がバランスのとれた二分木と考えることができ、ノードの総数は になりますが、この場合はよくわかりません。forO(n)2*n - 1

于 2012-05-21T05:48:50.597 に答える