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

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

为了评估复杂性，让我们关注执行的递归调用的数量，让我们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) - 但这仍然不能使其成为可接受的实现:)

Answer 2

假设

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

在加泰罗尼亚语 （n） 的 for 循环中，加泰罗尼亚语 （i） 执行 n-1 次，其中 i 的值从 1 到 n-1，

加泰罗尼亚语 （n-i） 执行 n-1 次，其中 n-i 的值从 n-1 到 1。简而言之，加泰罗尼亚语（i）和加泰罗尼亚语（n-i）等于所有加泰罗尼亚语（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 3

我的过程与@hk6279的过程非常相似，但我相信更容易理解，因为我从代码本身开始。我开始在代码中定义递归关系，然后替换它。

我还从@hk6279的方法中删除了所有 + k + c 变量，因为它为方程增加了噪声，最后所有这些变量都将被排除。

递归关系

T(n) => 1             -> n = 1
        T(i) * T(n-i) -> n > 1; for i in 1..n-1

可视化何时 n> 1

T(n) = [T(1) + T(2) + T(3) + .... + T(n-2) + T(n-1)] + [T(n-1) + T(n-2) + .... + T(3) + T(2) + T(1)]
T(n) = [T(1) + T(2) + T(3) + .... + T(n-2) + T(n-1)] + [T(1) + T(2) + T(3) + .... + T(n-2) + T(n-1)]
T(n) = 2 * [T(1) + T(2) + T(3) + .... + T(n-2) + T(n-1)]

什么是 T（n-1） ？

T(n-1) = 2 * [T(1) + T(2) + T(3) + .... + T(n-2)]

替换为 T（n-1）

T(n) = 2 * [T(1) + T(2) + T(3) + .... + T(n-2) + T(n-1)]
T(n) = 2 * [T(1) + T(2) + T(3) + .... + T(n-2)] + 2 * [T(n-1)]
T(n) = T(n-1) + 2 * [T(n-1)]
T(n) = 3 * T(n-1)

什么是 T（n-2） ？

T(n-2) = 2 * [T(1) + T(2) + T(3) + .... + T(n-3)]

替换为 T（n-2）

T(n) = 3 * [2 * [T(1) + T(2) + T(3) + .... + T(n-3) + T(n-2)]]
T(n) = 3 * [2 * [T(1) + T(2) + T(3) + .... + T(n-3)] + 2 * T(n-2)]]
T(n) = 3 * [T(n-2) + 2*T(n-2)]
T(n) = 3 * [3 * T(n-2)]
T(n) = 3^2 * T(n-2)

替换为 T（n-k）

T(n) = 3^k * T(n-k)
if n - k = 1 => k = n + 1
T(n) = 3^(n+1) * T(n-n+1)
T(n) = 3^(n+1) * T(1)
T(n) = 3^(n+1) * 1

时间复杂度

O(3^n)