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

Question

以下函数生成 catalan numbers 中的第 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

为了评估复杂性，让我们关注执行的递归调用次数，让 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) 通过注意循环中的所有项(除了中间一个) 被计算了两次——但这仍然不能使它成为一个可接受的实现:)