algorithm - 确定以下代码的运行时间（内部循环递归）

Question

我有以下代码，需要确定这个算法的运行时间。

int res=0; 
if (n <= 1) 
    return 1;
for (int i = 0; i < n; i++) 
    res += Catalan(i) * (Catalan(n - i - 1); 
return res;

由于递归内部的循环，我很难确定运行时间。我知道我需要将其转换为回归公式，然后对其进行分析，但我不知道该怎么做。

Answer 1

让我们将您的功能简化为：

    for (int i=0; i< n; i++) 
        res += Catalan(i)*(Catalan(i-1); 
    return res;

这种简化不应影响时间复杂度。

让 n = 1：

   1 
   /\
  0  0

然后我们将有 3 次加泰罗尼亚语函数调用。

如果 n = 2，那么对于 Catalan(i)，我们将有：

     2
     /
    1 
   /\ 
  0 0 

对于加泰罗尼亚语（i-1）

   1 
   /\
  0  0

所以总的来说，我们将拥有：

     2      
     /\    
    1  1   
   /\  /\  
  0 0 0  0 

如果 i=3，则：

          3
       /     \
      2       2 
     /\       /\
    1  1     1  1
   /\  /\    /\ /\
  0 0 0  0  0 0 0 0

在我看来，这很O(2^n)复杂

Answer 2

要获得第一个想法，请使用不同大小的输入对其进行分析。

如果您根据输入的大小绘制图形运行时，您将很容易知道它是 O(N) 还是 O(N²) 之类的东西。

然后你知道你在寻找什么复杂性，仔细查看你的代码以找到你观察的格式证明。