加泰罗尼亚数字，递归函数时间复杂度

Question

以下函数产生加泰罗尼亚语数字中的第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;
}

注意：我知道这是计算加泰罗尼亚数的最坏方法。

Answer 1

认为

1. 除了for循环之外的任何步骤都是k；
2. for循环中的求和和倍数是c和
3. 加泰罗尼亚语(r) 是T(r)

在 catalan(n) 的 for 循环中，catalan(i) 执行 n-1 次，其中 i 的值从 1 到 n-1，catalan(ni) 执行 n-1 次，其中 ni 的值从 n-1 到 1简而言之，catalan(i) 和catalan(ni) 等于所有catalan(x) 的两倍，其中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)

Answer 2

为了评估复杂度，让我们关注执行的递归调用的数量let C(n)。

呼叫n表示完全2(n-1)递归的呼叫，每个呼叫都会增加自己的成本2(C(1)+C(2)+...C(n-1))。

呼叫n+1表示完全2n递归的呼叫，每个呼叫都会增加自己的成本2(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)到O(2^n)，但这仍然不能使它成为可接受的实现:)