6

次の関数は、カタロニア語の n 番目の数字を生成します。この関数の正確な時間複雑度関数は何ですか、または自分でそれを見つけるにはどうすればよいですか?

int catalan(int n)
{
    if (n==0 || n==1)
        return 1;

    int sum = 0;
    for(int i=1;i<n;i++)
        sum += catalan(i)*catalan(n-i);
    return sum;
}

注: これがカタロニア語の数値を計算する最悪の方法であることはわかっています。

4

3 に答える 3

13

複雑さを評価するために、実行された再帰呼び出し let の数に注目しましょうC(n)。

の呼び出しは、それぞれが独自のコストを追加する、n正確に再帰的な呼び出しを意味します。2(n-1)2(C(1)+C(2)+...C(n-1))

の呼び出しは、それぞれが独自のコストを追加する、n+1正確に再帰的な呼び出しを意味します。2n2(C(1)+C(2)+...C(n-1)+C(n))

の違いによりC(n+1)-C(n) = 2+2C(n)、 と書くことができますC(n) = 2+3C(n-1)。

C(1) = 0
C(2) = 2+2C(1) = 2+3C(0) = 2
C(3) = 4+2(C(1)+C(2)) = 2+3C(2) = 8
C(3) = 6+2(C(1)+C(2)+C(3)) = 2+3C(3) = 26
C(4) = 8+2(C(1)+C(2)+C(3)+C(4)) = 2+3C(4) = 80
...
C(n) = 2n-2+2(C(1)+C(2)+...C(n-1)) = 2+3C(n-1)

この再発を簡単に解決するには、次のことに注意してください。

C(n)+1 = 3(C(n-1)+1) = 9(C(n-2)+1) = ...3^(n-2)(C(2)+1) = 3^(n-1)

したがって、n>1正確な式は

C(n) = 3^(n-1)-1

Catalan(1)(一定時間)の呼び出し回数もC(n)であり、加算または乗算の回数はC(n)/2それぞれ です。

O(3^n)ループ内のすべての項 (中央の項を除く) が 2 回計算されることに注意することで、複雑さを簡単に減らすことができO(2^n)ますが、それでも受け入れ可能な実装にはなりません :)

于 2014-12-09T08:21:26.023 に答える
9

推定

  1. for ループ以外のステップは k です。
  2. for-loop の総和と倍数は c であり、
  3. カタロニア語(r)はT(r)

catalan(n) の for ループでは、catalan(i) は i の値が 1 から n-1 の範囲で n-1 回実行し、catalan(ni) は ni の値が n-1 から 1 の範囲で n-1 回実行します。 . つまり、catalan(i) と catalan(ni) はすべての catalan(x) の 2 倍に等しく、x の値は 1 から n-1 です。

T(n) = 2(T(1) + T(2) + T(3) + ... + T(n-2) + T(n-1)) + k + (n-1)c
Similarly, 
T(n-1) = 2(T(1) + T(2) + T(3) + ... + T(n-2)) + k + (n-2)c

Reorder T(n) as 2(T(1) + T(2) + T(3) + ... + T(n-2)) + 2T(n-1) + k + (n-2)c + c
T(n) = 2(T(1) + T(2) + T(3) + ... + T(n-2)) + k + (n-2)c + 2T(n-1) + c
T(n) = T(n-1) + 2T(n-1) + c
T(n) = 3T(n-1) + c
T(n) = (3^2)T(n-2) + 3c + c
T(n) = (3^3)T(n-3) + (3^2)c + 3c + c
and so on...
T(n) = (3^(n-1))T(n-(n-1)) + c(3^0 + 3^1 + 3^2 + ... + 3^(n-2))
T(n) = (3^(n-1))T(1) + ((3^(n-1)-1)/2)c

したがって、時間複雑度はO(3 ^ N)

于 2014-12-09T06:44:21.380 に答える