29

再帰アルゴリズムの時間計算量を計算するにはどうすればよいですか?

int pow1(int x,int n) {
    if(n==0){
        return 1;
    }
    else{
        return x * pow1(x, n-1);
    }
}

int pow2(int x,int n) {
    if(n==0){
        return 1;
    }
    else if(n&1){
        int p = pow2(x, (n-1)/2)
        return x * p * p;
    }
    else {
        int p = pow2(x, n/2)
        return p * p;
    }
}
4

5 に答える 5

37

再帰関数を分析する (またはそれらを評価する) ことは、重要な作業です。(私の意見では) Don Knuths Concrete Mathematicsに良い紹介があります。

ただし、これらの例を分析してみましょう。

関数に必要な時間を与える関数を定義します。が、つまり の関数 がt(n)必要とする時間を表すとしましょう。pow(x,n)n

をt(0)=c呼び出すとpow(x,0)、( n==0) かどうかを確認してから 1 を返す必要があるため、これは一定の時間で実行できます (したがって定数c)。

ここで、他のケースを考えます: n>0. ここで を得るt(n) = d + t(n-1)．これは、 を再度チェックしn==1、 を計算pow(x, n-1し、したがって ( t(n-1)) を計算し、その結果に を掛ける必要があるためxです。チェックと乗算は一定時間 (定数) で実行でき、ニーズdの再帰計算が可能です。powt(n-1)

これで、用語を「展開」できますt(n)。

t(n) =
d + t(n-1) = 
d + (d + t(n-2)) = 
d + d + t(n-2) = 
d + d + d + t(n-3) =
... =
d + d + d + ... + t(1) =
d + d + d + ... + c

では、 に到達するまでにどのくらいかかりt(1)ますか? から開始しt(n)、各ステップで 1 を減算n-1するため、 に到達するにはステップが必要ですt(n-(n-1)) = t(1)。n-1一方、それは、定数 の倍数を取得しd、 にt(1)評価されることを意味しcます。

したがって、次のようになります。

t(n) =
...
d + d + d + ... + c =
(n-1) * d + c

したがってt(n)=(n-1) * d + c、O(n) の要素であることがわかります。

pow2マスターの定理を使用して行うことができます。アルゴリズムの時間関数は単調に増加すると想定できるためです。これt(n)で、 の計算に必要な時間が得られましたpow2(x,n)。

t(0) = c (since constant time needed for computation of pow(x,0))

n>0私たちが得るために

        / t((n-1)/2) + d if n is odd  (d is constant cost)
t(n) = <
        \ t(n/2) + d     if n is even (d is constant cost)

上記は次のように「簡略化」できます。

t(n) = floor(t(n/2)) + d <= t(n/2) + d (since t is monotonically increasing)

これはt(n) <= t(n/2) + d、マスターの定理を使用して解決できますt(n) = O(log n)(ウィキペディアのリンクにある「一般的なアルゴリズムへの適用」のセクションを参照してください。例「二分探索」)。

于 2010-04-25T17:42:32.950 に答える
12

最も単純なpow1から始めましょう。

O（1）で1回の実行を行う関数があります。（条件のチェック、戻り、乗算は一定時間です。）

あなたが残したのはあなたの再帰です。あなたがする必要があるのは、関数がそれ自体を呼び出すことになる頻度を分析することです。pow1では、N回発生します。N * O（1）= O（N）。

pow2の場合、これは同じ原則です。関数の1回の実行はO（1）で実行されます。ただし、今回は毎回Nを半分にします。これは、log2（N）回実行されることを意味します-事実上、ビットごとに1回です。log2（N）* O（1）= O（log（N））。

あなたを助けるかもしれない何かは、再帰が常に反復として表現できるという事実を利用することです（必ずしも非常に単純ではありませんが、それは可能です。私たちはpow1を次のように表現することができます

result = 1;
while(n != 0)
{
  result = result*n;
  n = n - 1;
}

これで、代わりに反復アルゴリズムが使用できるようになり、その方法で分析する方が簡単な場合があります。

于 2010-04-25T17:28:56.223 に答える
6

少し複雑かもしれませんが、通常の方法はマスターの定理を使用することだと思います。

于 2010-04-25T17:25:32.260 に答える
5

再帰を無視した両方の関数の複雑さはO（1）です。

最初のアルゴリズムの場合、再帰の深さはnと線形に相関するため、pow1（x、n）の複雑さはO（n）です。

2番目の複雑さはO（log n）です。ここでは、約log2（n）回繰り返します。2を捨てると、lognが得られます。

于 2010-04-25T17:25:50.073 に答える
0

だから私はあなたがxをn乗していると推測しています。pow1はO（n）を取ります。

xの値を変更することはありませんが、1になるまで毎回nから1を取ります（その後、戻るだけです）。これは、再帰呼び出しをn回行うことを意味します。

于 2010-04-25T17:28:44.070 に答える